GCJPURE - Your Rank is Pure

Pontius: You know, I like this number 127, I don't know why.
Woland: Well, that is an object so pure. You know the prime numbers.
Pontius: Surely I do. Those are the objects possessed by our ancient masters hundreds of years ago. Oh, yes, why then? 127 is indeed a prime number as I was told.
Woland: Not... only... that. 127 is the 31st prime number; then, 31 is itself a prime, it is the 11th; and 11 is the 5th; 5 is the 3rd; 3, you know, is the second; and finally 2 is the 1st.
Pontius: Heh, that is indeed... purely prime.

The game can be played on any subset S of positive integers. A number in S is considered pure with respect to S if, starting from it, you can continue taking its rank in S, and get a number that is also in S, until in finite steps you hit the number 1, which is not in S.

When n is given, in how many ways you can pick S, a subset of {2, 3, ..., n}, so that n is pure, with respect to S? The answer might be a big number, you need to output it modulo 100003.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each contains a single integer n.

Output

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

Limits

T ≤ 200.

2 ≤ n ≤ 500.

Sample

Input:
2
5
6

Output:
Case #1: 5
Case #2: 8

(All problem statements, input data and contest analyses from google code jam are licensed under the Creative Commons Attribution License.)


Added by:Shafaet
Date:2013-05-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Google Code Jam Round 1B 2010, Problem C

hide comments
2013-06-07 10:31:55 Shubham Rai
@nitish rao the 5th subset is (3,4,5).
2013-06-06 14:52:20 nitish rao
can anyone explain the first test case please.. i am getting only 4 subsets.. (5),(2,5),(2,3,5),(2,3,4,5)... whats the other one??
2013-05-21 20:15:23 (Tjandra Satria Gunawan)(曾毅昆)
if you feel than n≤500 is too small, try this one EGCJPURE with n≤10^5, also time limit is 100× longer ;-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.