Obcy skontaktowali się z ludźmi i wysłali wiadomość zawierającą odpowiedź na „Ostateczne pytanie o życie, wszechświat i całą resztę”.

Ludzie otrzymali $n$ bajtów (liczb całkowitych od 0 do 255 włącznie). Algorytm dekodowania jest następujący:

• Rozważmy wszystkie $n!$ permutacji otrzymanych bajtów.
• Potraktujmy każdą permutację jako liczbę zapisaną w systemie o podstawie 256. Liczby mogą być równe.
• Pomnóżmy wszystkie te liczby modulo 65 535.
• Wynik jest zdekodowaną wiadomością!

Dla każdego bajtu $i$ podana jest liczba $c_i$ otrzymanych bajtów o wartości $i$. Zdekoduj wiadomość.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $t$ ($1 \le t \le 100$) — liczbę zestawów danych. Następnie następuje opis zestawów danych.

Pierwsza linia każdego zestawu danych zawiera pojedynczą liczbę całkowitą $k$ ($1 \le k \le 256$) — liczbę bajtów $i$, dla których $c_i \neq 0$.

Każda z kolejnych $k$ linii zawiera dwie liczby całkowite $i, c_i$ ($0 \le i \le 255$, $1 \le c_i \le 10^9$). Gwarantuje się, że wszystkie podane wartości $i$ są różne.

Dla pozostałych $256 - k$ bajtów liczby $c_i$ są równe 0.

Gwarantuje się, że $\sum_{i=0}^{255} c_i = n \le 10^9$.

Wyjście

Dla każdego zestawu danych wypisz pojedynczą liczbę całkowitą — zdekodowaną wiadomość.

Przykład

Wejście 1

5
1
42 1
2
0 1
1 1
1
239 2
2
1 1
2 1
3
1 1
2 2
3 2

Wyjście 1

42
256
514
1284
61726