회문 수

윌리(Willi)는 프로그래밍 대회에 참가했습니다. 문제 중 하나는 주어진 문자열이 회문(palindrome)인지 판별하는 것이었습니다. 회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 똑같은 문자열을 말합니다. 이 문제를 풀어 필요한 승점을 얻은 윌리는, 남는 시간에 회문을 더 깊이 파고들기로 했습니다. 그는 수(number)도 회문이 될 수 있다는 것을 깨달았습니다. 예를 들어 $2375732$는 회문 수입니다.

얼마 후 윌리는 다음과 같은 사실을 발견했습니다. "어떤 수가 회문이 아니라면, 그 수의 자릿수를 뒤집은 수를 더해서 회문으로 만들 수 있다." 예를 들어 $134$는 회문이 아니지만, 뒤집은 수 $431$을 더하면 $565$가 되어 회문이 됩니다.

그런데 종이에 이것저것 시도하던 중, 이 방법이 한 번에 통하지 않는 수도 있음을 알게 되었습니다. 예를 들어 $370$은 뒤집은 수 $073 = 73$을 더하면 $443$이 되는데, 이는 회문이 아닙니다. 윌리의 해결책은 이렇습니다. 결과가 회문이 아니면, 뒤집어 더하는 과정을 회문이 될 때까지 반복하는 것입니다. 위 예에서는 $443 + 344 = 787$이 되어 회문이 됩니다.

하지만 이 과정이 모든 수에 대해 성공할까요?

윌리는 이 문제에 싫증이 나서 당신에게 도움을 청합니다. 구간 $[a, b]$ 안의 모든 수에 대해, 자릿수를 뒤집어 더하는 과정을 반복했을 때 회문이 되는지 확인하는 프로그램을 작성하세요. 프로그램이 반드시 종료하도록, 반복을 적용할 최대 횟수도 함께 주어집니다.

또한 윌리는 호기심이 많아서, 10진법뿐 아니라 임의의 진법으로 표현된 수에 대해서도 이를 확인하고 싶어 합니다.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스는 진법 $b$와 최대 반복 횟수 $l$이 공백으로 구분되어 주어지는 줄로 시작합니다. 그다음 줄에는 진법 $b$로 표기된 두 문자열 $s$, $e$가 공백으로 구분되어 주어지며, 이는 검사할 구간의 시작과 끝을 나타냅니다.

각 값의 범위는 다음과 같습니다.

• 진법 $b$: $2 \le b \le 30$
• 반복 횟수 $l$: $1 \le l \le 100$
• $s$와 $e$는 각각 $100$자리 미만이며, 구간 $[s, e]$에 포함된 수의 개수는 많지 않습니다(많아야 수백 개).

$9$보다 큰 자릿값은 소문자 알파벳으로 표기합니다($a = 10, b = 11, \dots$).

각 테스트 케이스에 대한 출력은 Scenario i: 형식의 줄로 시작합니다. 여기서 $i$는 $1$부터 시작하는 시나리오(테스트 케이스)의 번호입니다.

각 시나리오에서 구간 $[s, e]$에 속하는 모든 수에 대해, 자릿수를 뒤집어 더하는 과정을 반복하여 $l$번 이내에 회문이 되는지 확인합니다. (어떤 수가 이미 회문이면 $0$번 만에 종료한 것으로 봅니다.)

그다음 줄에는 $l$번의 반복 안에 회문이 됨을 보일 수 없는 수의 개수를 출력합니다.