## NOSQ - No Squares Numbers

no tags

A square free number is defined as a number which is not divisible by any square number.

For example, 13, 15, 210 are square free numbers, where as 25 (divisible by 5*5), 108 (divisible by 6*6), 18 (divisible by 3*3) are not square free numbers. However number 1 is not considered to be a square and is a squarefree number.

Now you must find how many numbers from number a to b, are square free and also have a digit d inside it.

For example for in the range 10 to 40 te squarefree numbers having digit 3 are 13, 23, 30, 31, 33, 34, 35, 37, 38, 39

### Input

The first line contains an integer T, which is the number of test-cases

Then follow T lines, each containing 3 integers a, b and d.

1 <= T <= 20,000

1 <= a <= b <= 100,000

0 <= d <= 9

### Output

Print one integer which is the required number as described in the problem statement.

### Example

```Input:
3
10 40 3
1 100 4
1 100000 7

Output:
10
9
26318```

 < Previous 1 2 3 4 Next > ican_code: 2020-09-11 09:00:18 i am not getting it , anyone knows where to find the solution ganeshpc: 2019-11-11 15:26:23 Getting TLE even after precomputation any suggestion?? sanket17: 2019-08-08 13:02:51 precomputation and t*(b-a) give tle cegprakash: 2019-05-09 21:57:32 author, plz remove spoilers from comments. Encourage others to stop giving away the solution. nadstratosfer: 2018-01-09 09:55:53 Great problem. Constraints are set wisely so a well designed Python code will pass in a fraction of a TL while a solution with clunky C-style loops with "same complexity" will probably TLE. I'd encourage Python beginners to experiment on this problem because learning the pythonic techniques that can significantly speed up your code here can make difference between AC and TLE in many other problems on SPOJ. m2do: 2018-01-07 12:51:23 nice problem :) dineshvssv: 2017-11-17 06:12:35 Nice problem use prefix array saurabh jain: 2016-09-14 23:52:22 nice problem Govind Lahoti: 2015-12-16 07:11:49 nice problem :) Rishabh Joshi: 2015-06-13 21:11:55 Really nice trick to optimize time. Nice problem!