Problem E
Onion Primes

Tor Project onion logo; Available for non-commercial use

An onion is a vegetable that is well known for its layers that can be peeled off to reveal … more layers of onion. This is the inspiration for the idea of an onion prime,¹ which is a prime number with an analogous layered structure. More precisely, a positive integer, $n$, is a $\textit{base-}b$ onion prime (bbop) if:

1. $n$ is prime

2. when written in $\textrm{base}~ b$ (with no leading zeros), then $n$ either (i) consists of $1$ or $2$ digits, or (ii) consists of $3$ or more digits, and when the first and last digits are removed (peeled off), the number that remains is a $\textrm{base-}b$ onion prime (and removing the first digit does not produce a leading zero)

For example, $2281$ is a $\textrm{base-}7$ onion prime because (1) it is prime, and (2) when the first and last digits are removed from its $\textrm{base-}7$ representation, namely $6436$, the result is $43$ $(=31$ in $\textrm{base}~ 10)$, which is a $\textrm{base-}7$ onion prime (because it is prime and consists of $2$ $(\textrm{base-}7)$ digits).

Given a base, $b$, and a closed interval, $[A,B]$, determine how many $\textrm{base-}b$ onion primes lie in the interval.

Input

The first line of input contains an integer, $T$, the number of test cases $(1 \leq T \leq 100)$. This is followed by $T$ lines, each of which contains three space-separated integers, $b~ A~ B$, where $b$ is a base $(2 \leq b \leq 10)$, and $A$ and $B$ are interval endpoints $(1 \leq A \leq B < 2^{31})$. All input numbers are in $\textrm{base}~ 10$.

Output

For each test case, output a line containing a single $(\textrm{base-}10)$ integer, the number of $\textrm{base-}b$ onion primes in $[A,B]$.

2
3 520 720
10 1 100

3
25