У 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$).

Новостворені роботи мають одну з 3 професій. Якщо номер $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<\cdots<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\times3^2\times5=90$. Робот $90$ має 10 учителів; разом із ним самим це 11 роботів. Серед них лише один політик — робот $15$; військові — роботи $3$ і $5$; науковців є 8, з номерами $2,6,9,10,18,30,45,90$.

Оцінювання

Вихідний файл містить три числа. Якщо програма правильно обчислила всі три, за тест нараховується 10 балів; якщо два — 7 балів; якщо одне — 4 бали; якщо жодного — 0 балів.