Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

In the game BioHazard 4, the president's daughter has been abducted by some crazy villagers. Leon S. Kennedy, the secret agent of White House, goes to rescue her. He keeps in contact with Hunnigan, the president's secretary.

But the time in their contact log has been encrypted, using the following method:

Count the number of seconds from 2000.01.01 00:00:00 to that time, assume this number is x. Then calculate x^{q}, modulo it by a prime number p. The remainder a is the encrypted number.

Your task is to help Leon write a program to decrypt the contact log, and tell him all the possible original time.

1. Remember that if the year can be divided evenly by 4 but can't be divided evenly by 100, or it can be divided evenly by 400, this year is a leap year. The February of a leap year has 29 days, while the February of other years has 28 days.

2. In this problem, if the year modulo 10 is 5 or 8, at the end of this year, there is one “leap second”, i.e., the second after 2005.12.31 23:59:59 is 2005.12.31 23:59:60, and after that second, it's 2006.01.01 00:00:00.

You may assume that from 2000.01.01 00:00:00 till that time, less than p seconds have passed.

But the time in their contact log has been encrypted, using the following method:

Count the number of seconds from 2000.01.01 00:00:00 to that time, assume this number is x. Then calculate x

Your task is to help Leon write a program to decrypt the contact log, and tell him all the possible original time.

1. Remember that if the year can be divided evenly by 4 but can't be divided evenly by 100, or it can be divided evenly by 400, this year is a leap year. The February of a leap year has 29 days, while the February of other years has 28 days.

2. In this problem, if the year modulo 10 is 5 or 8, at the end of this year, there is one “leap second”, i.e., the second after 2005.12.31 23:59:59 is 2005.12.31 23:59:60, and after that second, it's 2006.01.01 00:00:00.

You may assume that from 2000.01.01 00:00:00 till that time, less than p seconds have passed.

There are multiple test cases.

The first line of the input contains an integer T, meaning the number of the test cases.

For each test case, a single line of three integers: p, q, and a. (2<p≤1000000007, 1<q≤10, 0≤a<p, p is always a prime.)

The first line of the input contains an integer T, meaning the number of the test cases.

For each test case, a single line of three integers: p, q, and a. (2<p≤1000000007, 1<q≤10, 0≤a<p, p is always a prime.)

提交代码