問題文

太郎くんは、 $1$ から $N$ までの正整数が、文字列とみなしたときの辞書順で載っている数字辞書を持っています。 太郎くんは正整数 $K$ が辞書の何番目の項目として出てくるかが気になっています。太郎くんの代わりに $K$ が辞書順で何番目に出てくるかを求めてあげてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

$T$
$case_1$
$\vdots$
$case_T$

$N\ K$

入力は全て整数で以下の制約を満たす。

• $1\leq T \leq 10^4$
• $1\leq K \leq N < 10^{18}$

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

サンプル

3
12 4
999999999999999999 999999999999999999
999999999999999999 100000000000000000

7
999999999999999999
18