如果一个数 $x$ 的偶数位数字总数与 $\lfloor \sqrt{x} \rfloor$（$x$ 的平方根向下取整后的十进制表示）的偶数位数字总数之和，大于这两个数中奇数位数字的总数之和，则称 $x$ 为偶数占优数（even-dominant number）。

例如，$222213$ 是一个偶数占优数，因为 $222213$ 和 $\lfloor \sqrt{222213} \rfloor = 471$ 中偶数数字的总数为 $5$，大于奇数数字的总数 $4$。然而，$2$ 不是一个偶数占优数，因为 $2$ 和 $\lfloor \sqrt{2} \rfloor = 1$ 中偶数数字的总数为 $1$，等于奇数数字的总数。

请确定区间 $[\ell, r]$ 中偶数占优数的个数。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)：查询的数量。

接下来的 $t$ 行，每行包含两个整数 $\ell_i$ 和 $r_i$ ($1 \le \ell_i \le r_i \le 10^{12}$)，表示第 $i$ 次查询的区间。

输出格式

对于每个查询，输出一行，包含一个整数：给定区间内偶数占优数的个数。

样例

输入格式 1

1
1 10

输出格式 1

3