순수한 순위 (작은 입력)

폰티우스: 나는 127이라는 수가 마음에 든다. 이유는 나도 모르겠군.
볼란드: 그 수가 아주 순수하기 때문입니다. 소수는 아시지요.
폰티우스: 물론 안다. 수백 년 전 옛 스승들이 다루던 것들이지. 그런데 왜 하필 127인가? 127이 소수라는 말은 들었다.
볼란드: 그것... 만이... 아닙니다. 127은 31번째 소수입니다. 31 자신도 소수이고 11번째입니다. 11은 5번째, 5는 3번째, 3은 2번째, 마지막으로 2는 1번째입니다.
폰티우스: 허, 정말이지... 순수하게 소수답군.

이 게임은 양의 정수로 이루어진 집합 $S$ 위에서 진행한다. $S$의 원소 $x$에 대해, $S$의 원소를 오름차순으로 정렬하고 자리를 1부터 셌을 때 $x$가 놓인 자리를 $x$의 순위라 하고 $\mathrm{rank}_S(x)$로 쓴다.

$x$에서 출발해 현재 값을 그 값의 순위로 바꾸는 과정을 반복한다. 유한 번 만에 1에 도달하고 1에 도달하기 전에 거치는 값이 모두 $S$에 속하면, $x$는 $S$에 대해 순수하다고 한다. 1은 $S$에 속하지 않는다.

$n$이 주어진다. $\{2, 3, \dots, n\}$의 부분집합 $S$ 중 $n$이 $S$에 대해 순수한 것의 개수를 구하라. 개수가 클 수 있으므로 $100003$으로 나눈 나머지를 출력한다.

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

제한

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

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