Palapa 수
시간 제한2초메모리 제한512 MB
앞 두 자리 숫자의 합이 짝수이거나 마지막 두 자리가 소수인 N자리 수의 개수를 9973으로 나눈 나머지를 구한다.
문제
N (4 <= N <= 100) 자리 십진수 중에서 다음 조건을 만족하는 수를 Palapa 수 of N이라고 한다. 앞 두 자리 숫자의 합이 짝수이거나, 마지막 두 자리 숫자가 소수이거나, 둘 다이다. 맨 앞 자리에 0이 올 수 없다.
예를 들어,
- 1202는 Palapa 수 of 4이다. 4자리이고 마지막 두 자리 숫자 (02)가 소수이기 때문이다.
- 53160은 Palapa 수 of 5이다. 5자리이고 앞 두 자리 숫자의 합 (5 + 3 = 8)이 짝수이기 때문이다.
- 243913은 Palapa 수 of 6이다. 6자리이고, 앞 두 자리 숫자의 합 (2 + 4 = 6)이 짝수이며, 마지막 두 자리 숫자 (13)가 소수이기 때문이다.
- 0313은 Palapa 수가 아니다.
- 460025는 Palapa 수가 아니다.
N이 주어졌을 때, Palapa 수 of N의 개수를 9973으로 나눈 나머지를 출력한다.
입력
첫째 줄에 테스트 케이스의 수 T가 주어지고, 그다음 줄부터 각 테스트 케이스마다 정수 N (4 <= N <= 100)이 하나씩 주어진다.
출력
각 테스트 케이스마다 Palapa 수 of N의 개수를 9973으로 나눈 나머지를 출력한다.