题目描述

不能被任何（$\neq 1$ 的）平方数整除的数叫做 无平方数。如：$13,15,210$ 是 无平方数，$25,108,18$ 不是 无平方数。特别地，$1$ 也是 无平方数。

现在的问题是：请你输出$a$ 和$b$ 之间所有包含数字$d$ 的无平方数的个数。

如：$10$ 和$40$ 之间所有包含数字$3$ 的无平方数有：$13, 23, 30, 31, 33, 34, 35, 37, 38, 39$ 。

输入格式

第一行一个整数$T$ （$1\leq T \leq 20000$ ），表示数据组数。

接下来 $T$ 行，每行三个整数 $a,b,d$ ，意义如上

$1\leq a,b \leq 100000,0 \leq d \leq 9$

输出格式

一共输出 $T$ 行，每行一个整数代表每组询问的答案。

3
10 40 3
1 100 4
1 100000 7

10
9
26318