Migrated from Lutece 373 Concat Number

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Totalfrank is fond of numbers. One day, he found a kind of interesting numbers called Concat Number which is a concatenation of two numbers and divided exactly by the product of them. For example in decimal, 1352($10$) is a concatenation of 13($10$) and 52($10$), and 1352 is divided exactly by $13\times 52 = 676$; in octal, 53254($8$) is a concatenation of 53($8$) and 254($8$), and 53254($8$) = 22188($10$) is divided exactly by 53($8$) $\times$ 254($8$) $=$ 7396($10$). Note that the two numbers split from Concat Number are positive without leading zeros.

Now he wants to know the number of Concat Numbers in range $[L, R]$ ($L$ and $R$ are decimal numbers) in base $B$.

Input

The first line of the input is an integer $T$ ($T\leq 1000$), which stands for the number of test cases you need to solve.

Each case consists of three integers $B$, $L$, $R$ ($2\leq B\leq 100, 1\leq L\leq R\leq 10^{18}$) on a single line.

Output

For every test case, you should output Case #k: first, where $k$ indicates the case number and starts at $1$. Then output the answer.

Samples

2
10 1 100
8 1 100

Case #1: 5
Case #2: 7

Resources

The 9th UESTC Programming Contest Final