메시지 해독

외계인이 사람들과 접촉해서 "삶, 우주, 그리고 모든 것에 대한 궁극의 질문"의 답이 담긴 메시지를 보냈다.

사람들은 $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$이 보장된다.

각 테스트 케이스마다 해독된 메시지를 정수 하나로 출력한다.