In the year 3030, Macsy is deploying a batch of robots on Mars. At the 1st second, he transports Robot 1 to Mars. Robot 1 can manufacture other robots. At the 2nd second, Robot 1 manufactures the first robot—Robot 2. At the 3rd second, Robot 1 manufactures another robot—Robot 3. In every subsequent second, Robot 1 can manufacture a new robot. The robot manufactured at the $m$-th second is numbered $m$. We can call it Robot $m$.

Once a robot is manufactured, it immediately begins working. Robot $m$ rests every $m$ seconds. For example, Robot 3 rests at the 6th, 9th, 12th, ... seconds, and works at all other times.

When a robot rests, its memory is transplanted into the brains of the robots born at that time. For example, when Robot 6 is born, Robots 2 and 3 are resting, so Robot 6 receives a copy of the memories of Robots 2 and 3. We call Robots 2 and 3 the teachers of Robot 6.

If two robots have no teacher-student relationship and no common teacher, their knowledge is said to be mutually independent. Note: Robot 1's knowledge is independent of all other robots (because only Robot 1 manufactures robots), and it is not a teacher to any robot.

The independence number of a robot is the number of robots with a smaller index whose knowledge is mutually independent of it. For example, the independence number of Robot 1 is 0, the independence number of Robot 2 is 1 (Robot 1 is independent of it), and the independence number of Robot 6 is 2 (Robots 1 and 5 are independent of it; Robots 2 and 3 are its teachers, and Robot 4 shares a common teacher—Robot 2—with it).

Newly manufactured robots have 3 different professions. For a robot with index $m$: If $m$ can be factored into an even number of distinct odd prime factors, it is a politician (e.g., index 15). Otherwise, if $m$ is itself an odd prime or can be factored into an odd number of distinct odd prime factors, it is a soldier (e.g., index 3, index 165). * All other robots are scholars (e.g., index 2, index 6, index 9).

Robot $m$, born at the $m$-th second, wants to know the sum of the independence numbers of all politicians among itself and its teachers, the sum of the independence numbers of all soldiers among itself and its teachers, and the sum of the independence numbers of all scholars among itself and its teachers. Robot $m$ is too busy working to calculate this; can you help it?

To facilitate your calculation, Macsy has already performed the prime factorization of $m$. For ease of output, you are only required to output the sums modulo 10000.

Input

The first line of the input contains a positive integer $k$ ($1 \le k \le 1000$), where $k$ is the number of distinct prime factors of $m$. The following $k$ lines each contain two integers $p_i, e_i$, representing the $i$-th prime factor of $m$ and its exponent ($i = 1, 2, \dots, k$). $p_1, p_2, \dots, p_k$ are distinct primes, and $m = \prod_{i=1}^{k} p_i^{e_i}$. All prime factors are arranged in ascending order, i.e., $p_1 < p_2 < \dots < p_k$. In the input, $2 \le p_i < 10,000$ and $1 \le e_i \le 1,000,000$.

Output

The output consists of three lines. The first line is the sum of the independence numbers of all politicians among Robot $m$ and its teachers, modulo 10000. The second line is the sum of the independence numbers of all soldiers among Robot $m$ and its teachers, modulo 10000. The third line is the sum of the independence numbers of all scholars among Robot $m$ and its teachers, modulo 10000.

Examples

Input 1

3
2 1
3 2
5 1

Output 1

8
6
75

Note

$m = 2 \times 3^2 \times 5 = 90$. Robot 90 has 10 teachers, plus itself, for a total of 11 robots. Among them, the only politician is 15; the soldiers are 3 and 5; there are 8 scholars, with indices: 2, 6, 9, 10, 18, 30, 45, 90.

Subtasks

The output contains three numbers. If your program calculates all three numbers correctly, the test case is awarded 10 points; if it calculates two numbers correctly, it is awarded 7 points; if it calculates one number correctly, it is awarded 4 points; if it does not calculate any number correctly, the test case is awarded 0 points.