В 3030 году Macsy размещает на Марсе роботов.

В первую секунду он доставил на Марс робота номер 1. Этот робот умеет создавать других роботов.

Во вторую секунду робот номер 1 создал первого робота — робота номер 2.

В третью секунду робот номер 1 создал ещё одного робота — робота номер 3.

Далее каждую секунду робот номер 1 может создавать нового робота. Робот, созданный в секунду $m$, получает номер $m$. Будем называть его роботом номер $m$ или $m$-м роботом.

Сразу после создания робот начинает работать. Робот номер $m$ отдыхает каждые $m$ секунд. Например, робот номер 3 отдыхает в секунды $6,9,12,\ldots$, а всё остальное время работает.

Когда робот отдыхает, его память переносится в мозг робота, рождающегося в эту секунду. Например, при рождении робота номер 6 роботы номер 2 и 3 отдыхают, поэтому робот номер 6 получает копии их памяти. Назовём роботов номер 2 и 3 учителями робота номер 6.

Если два робота не связаны отношением учителя и ученика и у них нет общего учителя, их знания называются независимыми друг от друга. Обратите внимание: знания робота номер 1 независимы от знаний всех остальных роботов, поскольку только он умеет создавать роботов. Он также не является учителем ни одного робота.

Число независимости робота — количество роботов с меньшими номерами, знания которых независимы от его знаний. Например, число независимости робота номер 1 равно $0$, робота номер 2 — $1$, поскольку знания робота номер 1 независимы от его знаний, а робота номер 6 — $2$: независимы знания роботов номер 1 и 5; роботы номер 2 и 3 — его учителя, а у робота номер 4 с ним общий учитель — робот номер 2.

У новых роботов есть три различные профессии. Если номер робота $m$ можно представить произведением чётного количества различных нечётных простых чисел, он политик, например робот номер 15. Иначе, если $m$ само является нечётным простым числом или представимо произведением нечётного количества различных нечётных простых чисел, он военный, например роботы номер 3 и 165. Роботы со всеми прочими номерами — учёные, например роботы номер 2, 6 и 9.

Робот номер $m$, родившийся в секунду $m$, хочет узнать сумму чисел независимости всех политиков, всех военных и всех учёных среди него самого и его учителей. Но он занят работой, и у него нет времени на вычисления. Поможете ему?

Для удобства вычислений Macsy уже разложил $m$ на простые множители. Для удобства вывода требуется вывести только остатки от деления сумм на $10000$.

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

Первая строка входного файла robot.in содержит положительное целое число $k$, где $1\le k\le 1000$, — количество различных простых множителей $m$.

Следующие $k$ строк содержат по два целых числа $p_i,e_i$ — $i$-й простой множитель $m$ и его показатель степени, где $i=1,2,\ldots,k$. Числа $p_1,p_2,\ldots,p_k$ — различные простые числа, причём $m=\prod_{i=1}^k p_i^{e_i}$. Все простые множители перечислены по возрастанию: $p_1<p_2<\ldots<p_k$. Во входном файле $2\le p_i<10000$, $1\le e_i\le 1000000$.

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

Выходной файл robot.out состоит из трёх строк.

Первая строка содержит остаток от деления на $10000$ суммы чисел независимости всех политиков среди робота номер $m$ и его учителей.

Вторая строка содержит остаток от деления на $10000$ суммы чисел независимости всех военных среди робота номер $m$ и его учителей.

Третья строка содержит остаток от деления на $10000$ суммы чисел независимости всех учёных среди робота номер $m$ и его учителей.

Примеры

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

3
2 1
3 2
5 1

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

8
6
75

Примечание

$m=2\times 3^2\times 5=90$. У робота номер 90 есть 10 учителей, а вместе с ним самим получается 11 роботов. Среди них только один политик — номер 15; военные — номер 3 и 5; учёных восемь, их номера: $2,6,9,10,18,30,45,90$.

Подзадачи

Выходной файл содержит три числа. Если ваша программа правильно вычислит все три числа, за тест начисляется 10 баллов; если два числа — 7 баллов; если одно число — 4 балла; если ни одного числа — 0 баллов.