외계인이 사람들과 교신하여 "삶, 우주, 그리고 모든 것에 대한 궁극적인 질문"의 답이 담긴 메시지를 보냈습니다. 사람들은 $n$개의 바이트(0부터 255까지의 정수)를 받았습니다. 복호화 알고리즘은 다음과 같습니다.

• 받은 바이트들의 모든 $n!$가지 순열을 고려합니다.
• 각 순열을 256진법으로 쓰인 수로 간주합니다. 수들은 서로 같을 수 있습니다.
• 이 모든 수들을 곱한 값을 65 535로 나눈 나머지를 구합니다.
• 그 결과가 복호화된 메시지입니다!

각 바이트 $i$에 대하여, 받은 바이트 $i$의 개수 $c_i$가 주어집니다. 메시지를 복호화하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수 $t$ ($1 \le t \le 100$)가 주어집니다. 이어지는 각 테스트 케이스에 대한 설명이 나옵니다.

각 테스트 케이스의 첫 번째 줄에는 $c_i \neq 0$인 바이트 $i$의 개수 $k$ ($1 \le k \le 256$)가 주어집니다.

다음 $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