Blue Mary, the well-known astronaut, had sent Robot number 1 to Mars finally. Robot number 1 was so smart that he could make one robot per second.

Assume the time Robot number 1 arrived was second 1. At second i, Robot number 1 made a new Robot: Robot number i. (i>=2)

The new robots started work as soon as he was produced successfully. Robot number M only had a rest at second t, where t is a multiple of M. For example, Robot number 3 worked at second 4, 5, 7, 8, ... and had a rest at second 6, 9, ...

When a robot was having a rest, he could send his own informations to the newly produced robot. For example, when Robot number 6 was produced successfully, Robot number 2 and Robot number 3 are having a rest, so Robot number 6 would get information from Robot number 2 and number 3. We call Robot number 2 and number 3 are teachers of Robot number 6.

We call two Robots are independent if each of them wasn't a teacher of the other one and they had no common teachers. Please note that Robot number 1 was independent to any other robots and wasn't a teacher of any other robots, since only Robot number 1 could make robots.

The good number of Robot number M is the number of robots who was produced earlier than number M and independent to number M. Here are some examples:

The good number of Robot number 1 is 0.

The good number of Robot number 2 is 1. Number 1 was that robot.

The good number of Robot number 6 is 2. Number 1 and number 5 were those robots. Number 2 and number 3 were his teachers. Number 4 and him had a common teacher: number 2.

The Robots had 3 kinds of occupations. To Robot number M:

• If M can be written as the multiple of an even number of distinct odd primes, he was a businessman.
• If M can be written as the multiple of an odd number(1 included) of distinct odd primes, he was a hacker.
• All other robots were doctors.

Now Blue Mary was interesting to Robot number M. She wants to know the sum of good numbers of all businessmen, hackers and doctors among Robot number M and his teachers. She comes up with the answer quickly, and so can you.

Blue Mary is so kind that she gives you the prime divisors of M and you can only tell her the answers modudo 10000.

Input

The very first line contains a single integer T, the number of test cases.T blocks follow.

For each block, the first line contains a single integer K.K lines follow, each contains two integers p_i and a_i separated by a single space.

M = p₁^a₁ * p₂^a₂ * p₃^a₃ * ... * p_K^a_K.

You can assume that:

• All p_i are distinct primes and are less than 10,000.
• p₁ < p₂ < p₃ < ... n.
• All a_i are positive and no more than 1,000,000.
• 1 <= k <= 1000.

Output

For each test case, output 3 lines.

The first line contains a single integer denotes to the sum of good numbers of all businessmen among Robot number M and his teachers modudo 10000.

The second line contains a single integer denotes to the sum of good numbers of all hackers among Robot number M and his teachers modudo 10000.

The third line contains a single integer denotes to the sum of good numbers of all doctors among Robot number M and his teachers modudo 10000.

Example

Input:
1
3
2 1
3 2
5 1

Output:
8
6
75

Hints

In the sample input, M=2¹*3²*5¹=90. Robot number 90 has 10 teachers. Among Robot number 90 and his teachers, Robot number 15 is a businessman; number 3 and number 5 are hackers; all others are doctors, their numbers are 2, 6, 9, 10, 18, 30, 45, 90.