Palindromes

Willi took part in a programming contest. One of the tasks was to check whether given strings were palindromes — strings that read the same forwards and backwards. Solving it earned him the point he needed for victory, so he decided to spend some of his free time exploring palindromes further. He realized that numbers can be palindromes too: for example, $2375732$ is a palindrome.

After a while, Willi noticed the following: "If a number is not a palindrome, I can turn it into one by adding the number with its digits reversed." For instance, $134$ is not a palindrome, but adding its reverse $431$ gives $565$, which is a palindrome.

Playing with this on paper, he found numbers for which one step is not enough, such as $370$. Adding its reverse $073 = 73$ yields $443$, which is not a palindrome. His fix: if the result is not a palindrome, simply repeat the reverse-and-add step until a palindrome appears. In this example, $443 + 344 = 787$, a palindrome.

But does this always work?

Because Willi got bored with the problem, he asks for your help. Write a program that, for every number in an interval $[a, b]$, checks whether repeatedly reversing the number and adding it to itself produces a palindrome. To make sure your program terminates, he also gives you the maximum number of iterations to apply.

Since Willi is curious — and does not have to do the work himself — he wants you to check this for numbers written in an arbitrary base, not just decimal.

The first line of input contains the number of test cases $T$. Each test case starts with a line containing the base $b$ and the maximum number of iterations $l$, separated by a space. The next line contains two strings $s$ and $e$, separated by a space, written in base $b$; they denote the start and end of the interval to test.

The values satisfy the following limits:

• The base $b$ of the numbers: $2 \le b \le 30$.
• The number of iterations $l$: $1 \le l \le 100$.
• $s$ and $e$ each have fewer than $100$ digits, and the interval $[s, e]$ contains only a small number of values (at most a few hundred).

Digit values greater than $9$ are written with lowercase letters ($a = 10, b = 11, \dots$).

The output for each test case begins with a line Scenario i:, where $i$ is the number of the scenario, starting at $1$.

For each scenario, every number in the interval $[s, e]$ is tested to see whether repeatedly adding its digit-reversal produces a palindrome within $l$ iterations. (A number that is already a palindrome is considered to terminate in $0$ iterations.)

The next line contains the count of numbers for which no termination of the algorithm within $l$ iterations could be shown.