Robot Number M
Blue Mary, the well-known astronaut, had sent Robot No.1 to Mars finally.Robot No.1 was so smart that he could make one robot per second.
Assume the time Robot No.1 arrived was second 1. At second i, Robot No.1 made a new Robot: Robot No.i. (i>=2)
The new robots started work as soon as he was produced successfully. Robot No.M only had a rest at second t, where t is a multiple of M. For example, Robot No.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 No.6 was produced successfully, Robot No.2 and Robot No.3 are having a rest, so Robot No.6 would get informations from Robot No.2 and No.3. We call Robot No.2 and No.3 are teachers of Robot No.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 No.1 was independent to any other robots and wasn't a teacher of any other robots, since only Robot No.1 could make robots.
The good number of Robot No.M is the number of robots who was produced earlier than No.M and independent to No.M. Here are some examples:
The good number of Robot No.1 is 0.
The good number of Robot No.2 is 1. No.1 was that robot.
The good number of Robot No.6 is 2. No.1 and No.5 were those robots. No.2 and No.3 were his teachers. No.4 and him had a common teacher: No.2.
The Robots had 3 kinds of occupations. To Robot No.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 No.M. She wants to know the sum of good numbers of all businessmen, hackers and doctors among Robot No.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 pi and ai separated by a single space.
M = p1a1 * p2a2 * p3a3 * ... * pKaK.
You can assume that:
- All pi are distinct primes and are less than 10,000.
-
p1 < p2 < p3 < ... <pn.
</p</li>
- All ai are positive and no more than 1,000,000.
- 1 <= k <= 1000.
</ul> </div>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 No.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 No.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 No.M and his teachers modudo 10000.
Example
Input: 1 3 2 1 3 2 5 1
</p>Output: 8 6 75
Hints
In the sample input, M=21*32*51=90. Robot No.90 has 10 teachers.Among Robot No.90 and his teachers, Robot No.15 is a businessman; No.3 and No.5 are hackers; all others are doctors, their numbers are 2,6,9,10,18,30,45,90.