Please click here to download a PDF version of the contest problems. The problem is problem D in the PDF.

---

In the game BioHazard 4, the American 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 times.

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
3 2 1
3 2 2

Output:
Case #1:
2000.01.01 00:00:01
2000.01.01 00:00:02
Case #2:
Transmission error

---

hide comments

	Simes: 2023-02-04 15:05:26 I've extracted the problem from the PDF. I hope that's ok? If there are any mistakes or discrepancies, assume the PDF is correct.