注意

問題文

非負整数 $N$ の $d$ 進数字和 $f(N)$ を, ${\displaystyle N=\sum _{j=0}^M{a}_j{d}^j}$ を満たすような非負整数 $M$ と $M+1$ 個の $0$ 以上 $d-1$ 以下の整数 $a_0,\dots ,a_M$ を用いて, ${\displaystyle f(N)=\sum _{j=0}^M{a}_j}$ と定義する.

次に, 非負整数 $m,N$ に対して, $f^m(N)$ を以下のように定義する: $f^m(N)=\{\begin{array}{ll}f(f^{m-1}(N))& (m\ge 1)\\ N& (m=0)\end{array}$

また, 非負整数 $N$ の $d$ 進数字根 $N^{\ast }$ を ${\displaystyle N^{\ast }=\underset{m\to \mathrm{\infty }}{lim}{f}^m(N)}$ と定義する. では, 非負整数 $A,B(A\le B)$ に対して, ${\displaystyle \sum _{k=A}^B{k}^{\ast }}$ を求めよ.

なお, 数字根は全ての非負整数に対して一意に定まることが示される.

$T$ 個のテストケースについて答えよ.

例

• $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$
• $⋮$

制約

• $1\le T\le 2000$
• $2\le d\le {10}^9$
• $0\le A\le B\le {10}^9$
• $T,d,A,B$ は全て整数である.

入力

$T$

$dAB$

出力

各テストケースの出力後に改行すること.

サンプル

3
10 99 101
9 9 18
16 12345 67890

12
39
444375