Инопланетяне связались с людьми и отправили сообщение, содержащее ответ на «Главный вопрос жизни, вселенной и всего такого».

Люди получили $n$ байтов (целых чисел от 0 до 255 включительно). Алгоритм декодирования следующий:

• Рассмотрим все $n!$ перестановок полученных байтов.
• Рассмотрим каждую перестановку как число, записанное в системе счисления по основанию 256. Числа могут быть равны.
• Перемножим все эти числа по модулю 65 535.
• Результат — декодированное сообщение!

Для каждого байта $i$ вам дано количество $c_i$ полученных байтов со значением $i$. Пожалуйста, декодируйте сообщение.

Входные данные

Первая строка содержит единственное целое число $t$ ($1 \le t \le 100$) — количество наборов входных данных. Далее следует описание наборов данных.

Первая строка каждого набора данных содержит единственное целое число $k$ ($1 \le k \le 256$) — количество байтов $i$, для которых $c_i \neq 0$.

Каждая из следующих $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

1
42 1

Выходные данные 1

42

Входные данные 2

2
0 1
1 1

Выходные данные 2

256

Входные данные 3

1
239 2

Выходные данные 3

514

Входные данные 4

2
1 1
2 1

Выходные данные 4

1284

Входные данные 5

3
1 1
2 2
3 2

Выходные данные 5

61726