Decrypt Messages

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 xq, 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. Input 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.) Output The time. If there are multiple solutions, you must output all possible solutions in chronological order. If the solution doesn’t exist, output ‘Transmission error’ instead. See the sample output for further details. Sample Input 2 321 322 Sample Output Case #1: 2000.01.01 00:00:01 2000.01.01 00:00:02 Case #2: Transmission error