定义正整数 $x$ 的“数位积” $f(x)$ 为其所有数位上的数字之积。例如，$f(1234) = 1 \times 2 \times 3 \times 4 = 24$，且 $f(100) = 1 \times 0 \times 0 = 0$。

给定两个整数 $l$ 和 $r$，请计算以下值：

$$\left( \prod_{i=l}^{r} f(i) \right) \pmod{10^9 + 7}$$

如果你不了解 $\prod$ 的含义，上述表达式等同于：

$$(f(l) \times f(l + 1) \times \dots \times f(r)) \pmod{10^9 + 7}$$

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约为 $10^5$），表示测试数据的组数。对于每组测试数据：

仅一行，包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le 10^9$)，表示给定的两个整数。 输入整数不含前导零。

输出格式

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

样例

样例输入 1

2
1 9
97 99

样例输出 1

362880
367416

说明

对于第一组样例，答案为 $9! \pmod{10^9 + 7} = 362880$。

对于第二组样例，答案为 $(f(97) \times f(98) \times f(99)) \pmod{10^9 + 7} = (9 \times 7 \times 9 \times 8 \times 9 \times 9) \pmod{10^9 + 7} = 367416$。