外星人與人類取得了聯繫，並發送了一則訊息，其中包含了「生命、宇宙以及任何事情的終極答案」。

人們收到了 $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