外星人与人类取得了联系，并发送了一条包含“生命、宇宙以及一切的终极答案”的消息。

人们接收到了 $n$ 个字节（均为 $0$ 到 $255$ 之间的整数）。解码算法如下：

• 考虑接收到的字节的所有 $n!$ 种排列。
• 将每个排列视为一个 $256$ 进制的数。这些数可能相等。
• 将所有这些数相乘，结果对 $65\,535$ 取模。
• 最终结果即为解码后的消息！

对于每个字节 $i$，已知其出现的次数为 $c_i$。请解码该消息。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $k$ ($1 \le k \le 256$)，表示满足 $c_i \neq 0$ 的字节 $i$ 的数量。

接下来的 $k$ 行，每行包含两个整数 $i, c_i$ ($0 \le i \le 255, 1 \le c_i \le 10^9$)。保证所有给定的 $i$ 互不相同。

对于其余的 $256 - k$ 个字节，其对应的 $c_i$ 均为 $0$。

保证 $\sum_{i=0}^{255} c_i = n \le 10^9$。

输出格式

对于每个测试用例，输出一个整数，表示解码后的消息。

样例

输入格式 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

输出格式 1

42
256
514
1284
61726