Pontius: 你知道吗，我喜欢 127 这个数字，我也不知道为什么。

Woland: 嗯，那是一个非常纯粹的对象。你知道素数吧。

Pontius: 我当然知道。那是我们古代大师几百年前就掌握的对象。噢，是的，那又怎样呢？正如我所听说的，127 确实是一个素数。

Woland: 不仅仅是……那样。127 是第 31 个素数；然后，31 本身也是一个素数，它是第 11 个；11 是第 5 个；5 是第 3 个；3，你知道，是第 2 个；最后 2 是第 1 个。

Pontius: 嘿，那确实……纯粹地素。

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

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

样例

输入格式 1

2
5
6

输出格式 1

Case #1: 5
Case #2: 8