전화번호 판매

새 전화망을 만드는 사업에는 돈이 아주 많이 든다. 그래서 젊은 창업가 에이스 E. 엠미는 자신이 상표로 등록한 글로벌 고유 전화번호를 먼저 팔고, 그렇게 모은 돈을 기술 과제에 쏟기로 했다.

글로벌 전화번호는 자릿수가 많으므로 외워서 말하기 쉬운 번호일수록 값이 나간다. 그래서 번호마다 암기 점수를 매긴다. 번호 하나의 점수는 다음 규칙으로 정한다.

1. 점수를 0으로 둔다.

2. 길이가 $L$인 부분문자열마다, $L \ge 2$이고 그 부분문자열이 회문이면 점수에 $L$을 더한다. 회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다.

3. 길이가 $L$($L \ge 2$)로 같고 서로 겹치지 않으며 $B$가 $A$보다 뒤에 나오는 부분문자열 쌍 $A$, $B$마다, 아래 조건 가운데 성립하는 것 하나마다 점수에 $L$을 더한다.

   1. $A = B$이다.

   2. $A = B$이고 $B$가 $A$가 끝난 바로 다음 자리에서 시작한다.

   3. $A$가 $B$를 뒤집은 것과 같다.

엠미는 점수로 번호 값을 매기므로, 골드 클래스와 다이아몬드 클래스, 다이아몬드 클래스 플러스 플러스를 나누려면 어떤 점수를 가진 번호가 몇 개인지 세야 한다.

각 규칙은 부분문자열 하나 또는 부분문자열 쌍 하나마다 다른 적용과 무관하게 독립으로 작동한다. 길이 5인 회문은 길이 3인 회문을 반드시 포함하고, 규칙 3의 세 번째 조건에 맞는 쌍도 반드시 하나 만든다. 따라서 그런 다섯 글자 부분문자열의 점수는 최소 $5 + 3 + 2$이다. 이는 의도한 결과다. 총 길이가 같다면 짧은 무늬 여럿보다 긴 무늬 하나가 손님에게 더 매력이 있으므로 점수를 더 준다.

입력에는 테스트 케이스가 최대 11,000개 들어 있다. 각 테스트 케이스는 정수 $D$($0 < D < 12$)와 $S$($0 \le S < 1000$)가 공백 하나로 구분되어 한 줄에 주어진다. 이는 $D$자리 전화번호 가운데 암기 점수가 정확히 $S$인 것이 몇 개인지 묻는 질의다. 맨 앞자리가 0인 전화번호도 올바른 번호로 센다.

입력의 마지막 줄에는 공백으로 구분한 0이 두 개 놓이며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Among D digit phone numbers, there are N with score S.

$D$와 $S$는 입력으로 받은 값이고, $N$은 조건을 만족하는 전화번호의 개수다.