Description

Orange认为如果一个整数的各个数位和不超过k，则说明其是一个幸运数。请你求出1到n中幸运数的个数。

Format

Input

第一行包含一个整数 T，表示测试数据组数。 对于每组测试数据，包含两个整数n和k。

数据范围

对于 50% 的数据：

$1 \le n \le 10^6$

对于所有数据：

$1 \le T \le 10$

$1 \le n \le 10^{18}$

$1 \le k \le 10$

Output

对于每组测试数据，输出一行一个整数，表示答案。

Samples

6
100 3
100 4
100 5
200 3
200 4
200 5

10
15
21
16
25
36