복권 표

현우는 이번 콘서트 투어 표를 복권처럼 팔기로 했다. 규칙은 간단하다. 팬이 온라인으로 표를 사면 고유한 예약 번호를 받는다. 예약 번호는 공연마다 따로, 예약한 순서대로 0번부터 붙는다. 산 표가 당첨되면 콘서트에 갈 수 있고, 당첨되지 않으면 갈 수 없다.

당첨 번호는 현우가 무작위로 뽑는다. 그런데 현우가 쓰는 난수 생성기가 아주 느리다. 그래서 생성기를 부르는 횟수를 최소로 줄이려고 조금 이상하지만 공정한 추첨 방법을 만들었다.

한 공연의 예약이 끝나면 현우는 예약 수를 $M$이라 두고 $\{0, \dots, M-1\}$에서 무작위 정수 $Z$를 하나 뽑는다. 생성기는 이렇게 한 번만 부르면 된다. 그다음 당첨 여부를 좌우하는 정수 $r > 0$을 정한다.

$Z$와 $r$로 당첨표를 가리는 방법은 다음과 같다.

먼저 예약 번호 $0, \dots, M-1$과 $Z$를 길이가 $n$인 십진수 문자열로 바꾼다. $n$은 앞에 0을 붙이지 않고 쓴 $M-1$의 자릿수이다. 자릿수가 $n$보다 짧은 수는 앞을 0으로 채워 길이를 $n$으로 맞춘다.

예약 번호 $A$를 $a_1 \dots a_n$, $Z$를 $z_1 \dots z_n$이라고 하자. $A$가 당첨표이려면 두 문자열에 시작 위치가 같고 길이가 $r$ 이상인 공통 부분 문자열이 있어야 한다. 즉 $1 \le i \le n-r+1$이면서 $z_i \dots z_{i+r-1} = a_i \dots a_{i+r-1}$인 $i$가 존재해야 한다. 예를 들어 $Z = 56743$이고 $r = 3$이면 $06740$은 당첨표이지만 $56143$은 당첨표가 아니다.

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

첫째 줄에 공연의 수 $C$가 주어진다. ($1 \le C \le 5000$)

다음 $C$개 줄에 각 공연의 $M$, $Z$, $r$이 공백으로 구분되어 주어진다. ($0 < M \le 10^{18}$, $0 \le Z \le M-1$, $r \ge 1$) $r$은 항상 $M-1$의 자릿수 이하이다.

공연마다 당첨표의 개수를 한 줄에 하나씩 출력한다.