Your Rank is Pure (Large)

Pontius likes the number 127, and Woland explains why. 127 is the 31st prime. 31 is itself a prime, the 11th one. 11 is the 5th prime, 5 is the 3rd, 3 is the 2nd, and 2 is the 1st. Following the chain lands on 1, and 1 is not a prime.

This problem is about that chain. Fix a set $S$ of positive integers. The rank of an element $x$ of $S$ is the position of $x$ when the elements of $S$ are sorted in increasing order, counted from 1. Start at an element $x$ of $S$ and repeatedly replace the current number by its rank in $S$. If this reaches 1 after finitely many steps, then $x$ is pure with respect to $S$. Every number that appears before 1 has to belong to $S$ so that the next rank is defined, and 1 does not belong to $S$.

Given $n$, count the sets $S \subseteq \{2, 3, \dots, n\}$ for which $n$ is pure with respect to $S$. A number outside $S$ has no rank, so $n$ itself belongs to $S$. The count can be very large, so print it modulo $100003$.

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

Limits

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

For each test case, print one line of the form "Case #x: y". Here x is the case number starting from 1, and y is the count described above taken modulo $100003$.