Des extraterrestres ont contacté les humains et ont envoyé un message contenant la réponse à « La Grande Question sur la vie, l'univers et le reste ».

Les humains ont reçu $n$ octets (des entiers de 0 à 255 inclus). L'algorithme de décodage est le suivant :

• Considérons toutes les $n!$ permutations des octets reçus.
• Considérons chaque permutation comme un nombre écrit en base 256. Les nombres peuvent être égaux.
• Multipliez tous ces nombres modulo 65 535.
• Le résultat est le message décodé !

Pour chaque octet $i$, vous recevez le nombre $c_i$ d'octets $i$ reçus. Veuillez décoder le message.

Entrée

La première ligne contient un seul entier $t$ ($1 \le t \le 100$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un seul entier $k$ ($1 \le k \le 256$) — le nombre d'octets $i$ tels que $c_i \neq 0$.

Chacune des $k$ lignes suivantes contient deux entiers $i, c_i$ ($0 \le i \le 255, 1 \le c_i \le 10^9$). Il est garanti que toutes les valeurs $i$ données sont différentes.

Pour tous les autres $256 - k$ octets, les nombres $c_i$ sont égaux à 0.

Il est garanti que $\sum_{i=0}^{255} c_i = n \le 10^9$.

Sortie

Pour chaque cas de test, affichez un seul entier — le message décodé.

Exemples

Entrée 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

Sortie 1

42
256
514
1284
61726