Professor Shekhu has another problem for Akki today. He has given him three positive integers , and and wants him to calculate the remainder when is divided by . As usual, denotes the product of the first positive integers.
输入格式
The first line of the input gives the number of test cases, . lines follow. Each line contains three integers , and , as described above.
输出格式
For each test case, output one line containing Case #x: y, where is the test case number (starting from ) and is the answer.
样例
样例输入 1
2
2 1 2
3 3 2
样例输出 1
Case #1: 0
Case #2: 1
数据范围与提示
In Sample Case , the answer is the remainder when is divided by , which is .
In Sample Case , the answer is the remainder when is divided by , which is .
