Odd Numbers of Divisors

给出一个正奇数K，两个正整数low，high。

有多少整数属于[low, high]，且包含K个因子。

数据

C(0 < C < 1e5)，测试样例数。

(1 < K < 10000, 0 < low <= high < 1e10)。

输入

3

3 2 49

9 1 100

5 55 235

输出

4

2

1