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

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

공연의 예약이 완료되면, 현우는 예약 횟수를 M으로 두고, {0, ..., M-1}에서 랜덤 정수 Z를 하나 고른다. 이렇게 하면 생성기를 한 번만 호출해도 된다. 이제 현우는 당첨표에 직접 영향을 주는 정수 r > 0을 고른다.

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

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

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

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

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