Making a fun is a not a bad thing, but while making a fun if you disrespect someone then it will not be acceptable. Some of the North South University's students has done this type of wrong thing. So as a punishment they have to solve this problem. And you are a friend of them, so you should help them.

You will have N segments. Each one is connected in contiguous way. And we can number them from 1 to N. See the following figure:

Now you need to paint them, you have some colors, which are numbered from 1 to M. Now you need to count number of ways to paint the segments with the colors, such that this property preserves-

    U = color(i) + color(j)
    V = color(j) + color(k)
    U, V is Coprime.
    Here 1 <= i < j < k <= N and j = i + 1, k = j + 1
    And i, j, k indicates the index of segments and color(i) means the color you have painted on i th segment.

Input

Input starts with an integer T (≤ 2500), denoting the number of test cases.

Each case starts with a line containing two integers N, M.

1 <= N <= 50

1 <= M <= 50

Output

For each case, print the case number and the number of ways to paint the segments following above conditions. Since the result can be very large, you have to print the result modulo 1000003

Sample

Input
3
3 1
3 2
3 3

Output
Case 1: 0
Case 2: 4
Case 3: 14