Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2595
Ackerman's Function

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Ackerman's function is well known to all specialists in the theory of computation. It is the function in two positive integer arguments defined as follows:

It is not primitive recursive, more of that, A(i, i) grows faster than any primitive recursive function. In this problem your task is to calculate

A(n,m) mod t

for given t and several n and m. Here "x mod y" means the remainder of integer division of x by y - such r that 0 <= r < y and there exists integer q, such that x = qy + r.

Input

The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 20) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line of each test case contains t (1 <= t <= 100) and then several lines follow. Each of them contains two integers - n and m (1 <= m, n <= 100).

The last line of the test case contains two zeroes, it should not be processed.

Output

For each pair of integers in each test case, output its number followed by A(n, m) mod t. Use format shown in the sample output.

Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

Sample Input

2

3
3 3
2 7
1 18
0 0

2
1 1
1 2
1 3
0 0


Sample Output

Case 1: 1
Case 2: 2
Case 3: 0

Case 1: 0
Case 2: 0
Case 3: 0


Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6
Submit    Status