Người ngoài hành tinh đã liên lạc với con người và gửi một thông điệp chứa câu trả lời cho "Câu hỏi cuối cùng về Cuộc sống, Vũ trụ và Mọi thứ".

Con người đã nhận được $n$ byte (các số nguyên từ 0 đến 255). Thuật toán giải mã như sau:

• Xét tất cả $n!$ hoán vị của các byte đã nhận.
• Coi mỗi hoán vị là một số được viết trong hệ cơ số 256. Các số này có thể bằng nhau.
• Nhân tất cả các số này lại với nhau theo modulo 65 535.
• Kết quả thu được chính là thông điệp đã giải mã!

Với mỗi byte $i$, bạn được cho biết số lượng $c_i$ các byte $i$ đã nhận. Hãy giải mã thông điệp đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 100$) — số lượng bộ dữ liệu kiểm tra. Tiếp theo là mô tả của các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên duy nhất $k$ ($1 \le k \le 256$) — số lượng các byte $i$ sao cho $c_i \neq 0$.

Mỗi dòng trong $k$ dòng tiếp theo chứa hai số nguyên $i, c_i$ ($0 \le i \le 255, 1 \le c_i \le 10^9$). Đảm bảo rằng tất cả các giá trị $i$ được cho là khác nhau.

Đối với tất cả $256 - k$ byte còn lại, các số $c_i$ đều bằng 0.

Đảm bảo rằng $\sum_{i=0}^{255} c_i = n \le 10^9$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — thông điệp đã giải mã.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

42
256
514
1284
61726