Los alienígenas se comunicaron con los humanos y enviaron un mensaje que contiene la respuesta a "La pregunta definitiva sobre la vida, el universo y todo lo demás".

Las personas recibieron $n$ bytes (enteros desde 0 hasta 255 inclusive). El algoritmo de decodificación es el siguiente:

• Consideremos todas las $n!$ permutaciones de los bytes recibidos.
• Consideremos cada permutación como un número escrito en base 256. Los números pueden ser iguales.
• Multipliquemos todos estos números módulo 65 535.
• ¡El resultado es el mensaje decodificado!

Para cada byte $i$, se le da el número $c_i$ de bytes recibidos $i$. Por favor, decodifique el mensaje.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 100$) — el número de casos de prueba. A continuación, se describe cada caso de prueba.

La primera línea de cada caso de prueba contiene un único entero $k$ ($1 \le k \le 256$) — el número de bytes $i$ tales que $c_i \neq 0$.

Cada una de las siguientes $k$ líneas contiene dos enteros $i, c_i$ ($0 \le i \le 255$, $1 \le c_i \le 10^9$). Se garantiza que todos los valores $i$ dados son diferentes.

Para todos los demás $256 - k$ bytes, los números $c_i$ son iguales a 0.

Se garantiza que $\sum_{i=0}^{255} c_i = n \le 10^9$.

Salida

Para cada caso de prueba, imprima un único entero — el mensaje decodificado.

Ejemplos

Entrada 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

Salida 1

42
256
514
1284
61726