描述

沃洛季亚是一个怪异的男孩，他的品味也很奇特。在他看来，一个正整数是“美丽的”，当且仅当它能被它自己的每一个非零数字整除。我们不去争论这一点，而是计算给定范围内的美丽数字的数量。

输入规格

输入的第一行包含案例数量 $t$（$1 \leq t \leq 10$）。接下来的每一行包含两个自然数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 9 \cdot 10^{18}$）。

输出规格

输出应包含 $t$ 个数字——对查询的回答，每行一个数字——给定区间内美丽数字的数量（从 $l_i$ 到 $r_i$，包括两端）。

1
1 9

1
12 15

9

2