순위가 순수한 수 (Large)

폰티우스는 127이라는 수를 좋아하고, 볼란드는 그 이유를 이렇게 설명한다. 127은 31번째 소수다. 31도 소수이고, 11번째 소수다. 11은 5번째 소수, 5는 3번째 소수, 3은 2번째 소수, 2는 1번째 소수다. 이렇게 따라가면 1에 닿는데, 1은 소수가 아니다.

이 문제는 그 사슬을 다룬다. 양의 정수로 이루어진 집합 $S$를 하나 고정하자. $S$의 원소 $x$의 순위는 $S$의 원소를 오름차순으로 정렬했을 때 $x$가 놓이는 자리를 1부터 센 값이다. $S$의 원소 $x$에서 시작해 지금 수를 그 수의 $S$에서의 순위로 바꾸는 일을 되풀이했을 때 유한 번 만에 1에 닿으면, $x$는 $S$에 대해 순수하다고 한다. 1이 나오기 전에 나온 수는 모두 $S$에 속해야 다음 순위가 정의되고, 1은 $S$에 속하지 않는다.

$n$이 주어지면, $n$이 $S$에 대해 순수해지는 집합 $S \subseteq \{2, 3, \dots, n\}$이 몇 개인지 세어라. $S$에 속하지 않는 수는 순위가 없으므로 $n$은 반드시 $S$에 속한다. 개수가 매우 클 수 있으니 $100003$으로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 정수 $n$이 하나씩 주어진다.

제한

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

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 구한 개수를 $100003$으로 나눈 나머지다.