数论是纯数学的一个分支，主要致力于研究整数和整数值函数。德国数学家卡尔·弗里德里希·高斯曾说：“数学是科学的皇后，而数论是数学的皇后。”数论学家研究素数，以及由整数构成或定义为整数推广的对象的性质。

卡尔·弗里德里希·高斯肖像，由 C.A. Jensen 绘制。公有领域。

Chandra 是一位刚从大学毕业的初级数学家，她专攻数论。她一直以来的抱负是成为像高斯一样著名的数学家。在最近的研究中，她在数论领域发明了一个针对正整数 $x$ 的新函数 $f(x)$。设 $k$ 为 $x$ 的十进制表示中的位数，$d(x, i)$ ($1 \le i \le k$) 为 $x$ 在十进制表示下的第 $i$ 位数字。则：

$$f(x) = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} d(x, i) \cdot d(x, j)$$

Chandra 还发现了一个神秘的整数 $m$。她认为满足性质 $x \equiv f(x) \pmod m$ 的正整数对她的研究非常重要。她想找出满足 $L \le x \le R$ 且符合上述条件的整数 $x$ 的个数。她只需要知道这个数量对 $10^9 + 7$ 取模的结果，这也是她在研究中发现的另一个神秘整数。不幸的是，$L$ 和 $R$ 可能非常大，即使对于数学家来说，手工解决这个问题也是不可行的。为了发表论文并成为一名著名的数学家，Chandra 请你这位著名的程序员帮助她克服研究中的这个障碍。

输入格式

输入包含多组数据。第一行包含一个正整数 $T$，表示数据组数。

对于每组数据，第一行和第二行分别包含一个整数 $L$ 和 $R$ ($10 \le L \le R < 10^{5000}$)。第三行包含一个整数 $m$ ($2 \le m \le 60$)。

保证所有数据中 $R$ 的位数之和不超过 $5000$。

输出格式

对于每组数据，输出一行，包含一个整数，表示满足条件的整数 $x$ 的个数，对 $10^9 + 7$ 取模。

样例

样例输入 1

2
10
50
17
33
33
3

样例输出 1

2
1