제퍼디! 회문 소수 카테고리

어떤 수가 1보다 크고 1과 자기 자신으로만 나누어떨어지면 그 수를 소수(prime)라고 한다. 정의에 따라 0과 1은 소수가 아니다.

회문 수(palindromic number)란 그 표기를 앞에서 읽으나 뒤에서 읽으나 똑같은 문자열이 되는 수를 말한다.

당신은 "회문 소수" 카테고리의 문제를 준비하는 출제팀의 일원으로서, 제퍼디! 형식의 답과 그에 대응하는 질문을 생성하는 프로그램을 작성한다.

자릿수 $n$과 진법 $b$가 주어지면, $b$진법으로 표기했을 때 회문이면서 동시에 소수이고 그 값이 $2^{31}$ 미만인 $n$자리 수가 몇 개인지 센다. $n$자리 수에는 선행 0이 없으므로 가장 앞자리 숫자는 0이 아니다.

입력은 공백으로 구분된 여러 개의 수 쌍으로 이루어지며, 두 개의 0으로 이루어진 쌍으로 끝난다. 각 쌍에서 첫 번째 수는 고려할 자릿수 $n$이고, 두 번째 수는 수를 표기할 진법 $b$이다.

이 문제에서 세는 모든 회문 소수는 부호 있는 32비트 정수 범위 안에 들어간다(즉 값이 $2^{31}$ 미만이다).

진법 $b$는 2 이상 36 이하의 정수이다. 10보다 큰 진법은 16진법을 확장한 방식으로 다루며, 사용할 수 있는 숫자는 ['0'..'9']와 ['a'..'z']이다.

각 쌍마다 두 줄을 출력한다. 첫 줄은 자릿수와 진법을 나타내는 (제퍼디! 형식의) "답"이고, 둘째 줄은 찾은 회문 소수의 개수를 나타내는 "질문"이다. 연속한 두 쌍 사이는 빈 줄 하나로 구분한다.

n, b, count를 각각의 값으로 바꾸어 정확히 다음 형식으로 출력한다:

The number of n-digit palindromic primes < 2^31 in base b.
What is count?