25772번 - Decoding The Message 다국어

문제

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.

입력

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$.

출력

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

제한

힌트