Huge Numbers

Professor Shekhu has another problem for Akki today. He has given him three positive integers A, N and P and wants him to calculate the remainder when AN! is divided by P. As usual, N! denotes the product of the first N positive integers.

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers A, N and P, as described above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the answer.

• 1 ≤ T ≤ 100.

In Sample Case #1, the answer is the remainder when 21! = 2 is divided by 2, which is 0.

In Sample Case #2, the answer is the remainder when 33! = 36 = 729 is divided by 2, which is 1.