Note

Problem Statement

The base-$d$ digit sum $f(N)$ of a non-negative integer $N$ is defined as $\displaystyle f(N)=\sum_{j=0}^M a_j$, using a non-negative integer $M$ and $M+1$ integers $a_0,\dots,a_M$ between $0$ and $d-1$, inclusive, that satisfy $\displaystyle N=\sum_{j=0}^M a_j d^j$.

Next, for non-negative integers $m,N$, define $f^m(N)$ as follows: $\quad f^m(N)=\begin{cases} f(f^{m-1}(N)) & (m \geq 1) \\ N & (m=0) \end{cases}$

Also, the base-$d$ digital root $N^*$ of a non-negative integer $N$ is defined as $\displaystyle N^*=\lim_{m \to \infty} f^m(N)$. Now, for non-negative integers $A,B~(A \leq B)$, find $\displaystyle \sum_{k=A}^B k^*$.

It can be shown that the digital root is uniquely determined for every non-negative integer.

Solve $T$ test cases.

Example

• $f^0(N)=N=20201009$
• $f^1(N)=f(f^0(N))=f(N)=2+0+2+0+1+0+0+9=14$
• $f^2(N)=f(f^1(N))=f(f(N))=f(14)=1+4=5$
• $f^3(N)=f(f^2(N))=f(5)=5$
• $\vdots$

Constraints

• $1 \leq T \leq 2000$
• $2 \leq d \leq 10^9$
• $0 \leq A \leq B \leq 10^9$
• $T,d,A,B$ are all integers.

Input

$T$

$d~A~B$

Output

Print a newline after the output of each test case.

Sample

3
10 99 101
9 9 18
16 12345 67890

12
39
444375