COLORSEG  Coloring Segments
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
Output for Sample Input
3
3 1
3 2
3 3
Case 1: 0
Case 2: 4
Case 3: 14
hide comments
smso:
20200606 09:21:29
Deal with nasty TLE by precomputing. 

karthik1997:
20171223 10:24:20
Really Good Question . I wonder , how much was the complexity of those , who solved it , in less than 10ms (0.00 s) 

hodobox:
20170426 02:23:49
Pretty cool, haven't seen anything quite like this before :) 

mdaamir151:
20170308 18:43:19
@Faiyaz I am getting sigsev ( runtime error ) on submission . It runs just fine on my machine!


naruto09:
20160711 02:02:50
great question..!! 

Rishi Vikram:
20160312 21:37:31
For those getting WA, answer for n<=2 is NOT zero. 

parijat bhatt:
20150605 21:20:53
Francky pls help. 

parijat bhatt:
20150605 21:20:19
could any one tell me the complexity per test case. thanks 

Francky:
20141114 23:43:57
@Mitch : In the submission list, when I'm logged (or not!), I only see 11832574, 11832563, 11832471 submissions from you, those 3 are WA. I don't see your others ones. If it can help...


Mitch Schwartz:
20141114 22:48:21
@Ahmad Faiyaz: It is very rude to change the source limit after publication and then disqualify correct longer codes. You should have thought about those things before publishing.

Added by:  Faiyaz 
Date:  20140626 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 