Description

Pontius：你知道吗，我喜欢这个数字 127，我也不知道为什么。
Woland：嗯，那是一个非常纯粹的对象。你知道质数吧。
Pontius：当然知道。那些是我们古代大师几百年前拥有的对象。哦，是的，为什么呢？127 的确是个质数，就像我被告知的那样。
Woland：不仅如此。127 是第 31 个质数；然后，31 本身也是质数，它是第 11 个；11 是第 5 个；5 是第 3 个；3，你知道，是第二个；最后 2 是第一个。
Pontius：呵，这确实……纯粹的质数。

这个游戏可以在任意正整数子集 $s$ 上进行。对于集合 $s$，如果一个数在 $s$ 中，从它开始，不断取它在 $s$ 中的排名，并且得到的数也在 $s$ 中，直到有限步后得到数字 1（1 不在 $s$ 中），那么这个数被称为相对于 $s$ 是纯粹的。

给定 $n$，有多少种方式可以选择 $s$，$s$ 是 $\{2, 3, ..., n\}$ 的一个子集，使得 $n$ 相对于 $s$ 是纯粹的？答案可能很大，你需要输出答案对 100003 取模的结果。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 行，每行包含一个整数 $n$。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试编号（从 1 开始），$y$ 是如上所述的答案。

2
5
6

Case #1: 5
Case #2: 8

Hint

数据范围

• $T \leqslant 100$。

小数据集（14 分，测试点 1 - 可见）

• 时间限制：3 秒。
• $2 \leqslant n \leqslant 25$。

大数据集（30 分，测试点 2 - 隐藏）

• 时间限制：6 秒。
• $2 \leqslant n \leqslant 500$。

由 ChatGPT 4.1 翻译