宇宙人が地球人と交信し、「生命、宇宙、そして万物についての究極の疑問」の答えを含むメッセージを送ってきた。 人々は $n$ バイト（0 から 255 までの整数）のデータを受信した。復号アルゴリズムは以下の通りである。

• 受信したバイトの $n!$ 通りの順列すべてを考える。
• 各順列を 256 進法で書かれた数とみなす。数は等しくなることもある。
• これらのすべての数を 65535 を法として掛け合わせる。
• その結果が復号されたメッセージである！

各バイト $i$ について、受信したバイト $i$ の個数 $c_i$ が与えられる。メッセージを復号せよ。

入力

入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 100$) が含まれる。続いて各テストケースの説明が続く。

各テストケースの最初の行には、$c_i \neq 0$ となるバイト $i$ の個数 $k$ ($1 \le k \le 256$) が含まれる。

続く $k$ 行のそれぞれには、2 つの整数 $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