파워베이스 표기법

수를 적을 때 흔히 쓰는 방식은 오른쪽에서 왼쪽으로 자리마다 가중치가 커지는 자리값 표기법이다. 파워베이스 표기법은 이와 달리 숫자를 왼쪽에서 오른쪽으로 적고, $p$번째 자리에 놓인 숫자 $d$의 값을 $d^p$로 본다. 보통 100이라고 적는 정수는 파워베이스 표기법에서 983이 된다. $9^1 + 8^2 + 3^3 = 100$이기 때문이다.

길이가 $L$인 파워베이스 표기는 쓸 수 있는 숫자 집합에서 고른 숫자 $d_1, d_2, \dots, d_L$을 늘어놓은 것이고, 그 값은 $d_1^1 + d_2^2 + \dots + d_L^L$이다. 모든 자리에 숫자가 하나씩 들어가므로 길이가 $L$인 표기는 숫자를 정확히 $L$개 쓴다.

파워베이스 표기법은 수를 어떤 진법으로 적었는지 알 필요도, 가정할 필요도 없다는 장점이 있다. 자리값 표기법의 100은 진법이 10이면 백이고 진법이 2이면 4이지만, 파워베이스 표기법의 983은 백 말고 다른 수가 될 수 없다.

진법이 없으니 어떤 숫자를 쓸지도 자유롭다. 파워베이스 수는 0과 1 없이 적는 경우가 많지만, 원칙적으로는 어떤 숫자 집합이든 쓸 수 있다. 다만 쓸 수 있는 숫자를 제한하면 어떤 값은 파워베이스 표기가 아예 없거나, 있어도 일정 길이보다 짧게 적을 수 없다. 예를 들어 숫자 2부터 9까지를 쓰면 2 이상 10000 이하의 모든 값을 7자리 안에 적을 수 있고, 그중 31개만 7자리를 다 써야 한다. 반면 숫자 2부터 7까지만 쓰면 값 25는 길이에 상관없이 파워베이스 표기가 없다.

주어진 숫자 집합으로 정해진 자리 수 이하의 파워베이스 표기를 만들 수 없는 정수가 몇 개인지 세는 프로그램을 작성하시오.

입력은 여러 개의 테스트로 이루어진다. 각 테스트의 첫 줄에는 검사할 첫 값과 마지막 값을 나타내는 정수 두 개가 공백 하나로 구분되어 주어진다. 두 값 모두 $1 \le n \le 100000$이고, 마지막 값은 첫 값보다 작지 않다. 0 두 개만 있는 줄이 나오면 입력이 끝난다.

각 테스트의 둘째 줄에는 살펴볼 파워베이스 표기의 최대 길이 $m$($2 \le m \le 15$)이 주어진다. 셋째 줄에는 파워베이스 표기에 쓸 수 있는 숫자를 나열한 문자열이 주어진다. 이 문자열에는 숫자 문자 0부터 9까지와 대문자 A부터 Z까지가 들어갈 수 있고, 대문자는 10부터 35까지의 숫자 값을 뜻한다. 문자는 숫자 값이 엄격히 증가하는 순서로 놓인다. 예를 들어 문자열 1248GW는 숫자 값 1, 2, 4, 8, 16, 32를 쓸 수 있다는 뜻이다.

각 테스트마다 한 줄씩 출력한다. 줄 앞부분은 Test k: 형태이고 $k$는 1부터 매기는 테스트 번호이다. 그다음 공백 하나를 두고, 그 테스트의 길이 제한과 숫자 집합으로는 표기할 수 없는 값이 범위 안에 몇 개인지 적는다.