K. Decoding The Message
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Aliens connected with people and sent a message containing the answer to "The Ultimate Question of Life, the Universe, and Everything".

People received $$$n$$$ bytes (integers from $$$0$$$ to $$$255$$$ inclusive). The decoding algorithm is the following:

  • Let us consider all $$$n!$$$ permutations of received bytes.
  • Consider each permutation as a number written in base $$$256$$$. Numbers can be equal.
  • Multiply all these numbers modulo $$$65\,535$$$.
  • The result is the decoded message!

For each byte $$$i$$$, you are given the number $$$c_i$$$ of received bytes $$$i$$$. Please decode the message.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer $$$k$$$ ($$$1 \leq k \leq 256$$$) — the number of bytes $$$i$$$ such that $$$c_i \neq 0$$$.

Each of the next $$$k$$$ lines contains two integers $$$i$$$, $$$c_i$$$ ($$$0 \leq i \leq 255$$$, $$$1 \leq c_i \leq 10^9$$$). It is guaranteed that all given values $$$i$$$ are different.

For all other $$$256 - k$$$ bytes, the numbers $$$c_i$$$ are equal to $$$0$$$.

It is guaranteed that $$$\displaystyle \sum\limits_{i=0}^{255} c_i = n \leq 10^9$$$.

Output

For each test case, print a single integer — the decoded message.

Example
Input
5
1
42 1
2
0 1
1 1
1
239 2
2
1 1
2 1
3
1 1
2 2
3 2
Output
42
256
514
1284
61726