시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 2 2 25.000%

문제

본 조비 2013 투어를 기획하는 현우는 표를 복권처럼 팔기로 결정했다. 규칙은 매우 간단하다. 팬은 온라인으로 표를 구매하고, 구매하면 고유한 예약 번호를 받게 된다. 모든 공연의 예약 번호는 0부터 예약한 순서대로 주어진다. 구매한 표가 당첨이 되면 콘서트에 갈 수 있는 것이고, 아니면 콘서트에 갈 수 없는 것이다.

현우는 당첨 표의 번호를 랜덤으로 뽑는다. 하지만, 현우가 사용하는 랜덤 숫자 생성기는 매우 느리다. 따라서, 생성기를 호출하는 횟수를 최소로 하기 위해서, 현우는 이상하지만 공정하게 당첨표를 뽑는 방법을 만들었다.

공연의 예약이 완료되면, 현우는 예약횟수 M을 알 수 있고, {0, ..., M-1}에서 랜덤 정수 Z를 하나 고른다. (팬은 0~M-1 사이의 예약 번호를 받게 된다) Z는 현우가 유일하게 뽑는 숫자이다. 이제 현우는 당첨표에 큰 영향을 주는 정수 r > 0을 결정한다.

Z와 r을 이용해서 당첨표를 뽑는 방법은 다음과 같다.

먼저, 예약 번호 0,...,M-1과 Z를 길이가 n인 10진수로 바꾼다. n은 M-1의 길이이며, 0이 앞에 붙을 수 없다. 길이가 n보다 작은 숫자는 앞에 0을 붙여 길이를 모두 같게 만든다.

a1...an이 예약 변호 A이고, z1...zn이 Z일 때, A가 당첨표가 되려면, z1...zn과 a1...an에 시작 위치가 같으면서 길이가 r 이상인 공통 부분 문자열이 존재해야 한다. 즉, 1 ≤ i ≤ n-r+1인 i에 대해서, zi...zi+r-1 = ai...ai+r-1이 존재해야 한다. 예를 들어, Z = 56743이고, r = 3인 경우에 06740은 당첨표 이지만, 56143은 당첨이 아니다.

M, Z, r이 주어졌을 때, 당첨표의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공연의 수 C가 주어진다. (1 ≤ C ≤ 5000) 다음 C개 줄에 대해서, 각 공연의 M, Z, r이 주어진다. (0 < M ≤ 1018, 0 ≤ Z ≤ M-1, r ≥ 1) r은 항상 M-1의 길이보다 작거나 같다.

출력

각 공연에 대해서, 당첨표의 개수를 출력한다.

예제 입력

8
89 32 1
67 49 1
67 45 2
1000 23 1
1000 401 2
1000 54 2
3571 2 3
3571 976 3

예제 출력

18
15
1
271
19
19
13
12

힌트