P13395 [GCJ 2010 #1B] 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.

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

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 \leqslant 100.$ **Small dataset (14 Pts, Test set 1 - Visible)** - Time limit: ~~30~~ 3 seconds. - $2 \leqslant n \leqslant 25.$ **Large dataset (30 Pts, Test set 2 - Hidden)** - Time limit: ~~60~~ 6 seconds. - $2 \leqslant n \leqslant 500.$