당신의 순위는 순수하다

Pontius: 있잖아, 나는 이 수 127이 마음에 들어. 왜인지는 모르겠지만. Woland: 그래, 정말 순수한 대상이지. 소수에 대해서는 알고 있겠지. Pontius: 물론 알지. 그것들은 수백 년 전 우리의 고대 스승들이 소유했던 대상들이잖아. 아, 그래, 그런데 왜? 내가 듣기로 127은 정말 소수인데. Woland: 그게... 전부가... 아니야. 127은 31st 소수이고, 다음으로 31 자체도 소수이며 11th이고, 11은 5th이고, 5은 3rd이고, 알다시피 3은 두 번째이고, 마지막으로 2은 1st야. Pontius: 허, 그건 정말... 순수하게 소수로군.

이 게임은 양의 정수로 이루어진 임의의 부분집합 S에서 할 수 있다. S에 속한 어떤 수에서 시작하여, S에서 그 수의 순위를 계속 취해 얻은 수가 역시 S에 속하는 과정을 반복하다가, 유한한 단계 후에 S에 속하지 않는 수 1에 도달할 수 있다면, 그 수는 S에 대해 순수하다고 간주한다.

n이 주어질 때, {2, 3, ..., n}의 부분집합 S을 골라 n이 S에 대해 순수하도록 하는 방법은 몇 가지인가? 답은 큰 수일 수 있으므로, 이를 100003로 나눈 나머지를 출력해야 한다.

제한

메모리 제한: 1GB. T ≤ 100.

작은 데이터셋(테스트 세트 1 - 공개)

시간 제한: 30초. 2 ≤ n ≤ 25.

큰 데이터셋(테스트 세트 2 - 비공개)

시간 제한: 60초. 2 ≤ n ≤ 500.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 하나의 정수 n이 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 위에서 설명한 답이다.