Your Rank is Pure (Small)

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 our ancient masters possessed 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 runs on a set $S$ of positive integers. For an element $x$ of $S$, sort the elements of $S$ in increasing order and count positions from 1. The position of $x$ in that order is the rank of $x$, written $\mathrm{rank}_S(x)$.

An element $x$ of $S$ is pure with respect to $S$ when the sequence that starts at $x$ and repeatedly replaces the current value by its rank in $S$ reaches 1 after finitely many steps, and every value it visits before reaching 1 belongs to $S$. The number 1 never belongs to $S$.

You are given $n$. Count the subsets $S$ of $\{2, 3, \dots, n\}$ for which $n$ is pure with respect to $S$. The count can be large, so print it modulo $100003$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one integer $n$.

Limits

• $T \le 100$
• $2 \le n \le 25$

For each test case, print one line of the form Case #x: y, where x is the test case number starting from 1 and y is the count described above.