NOSQ  No Squares Numbers
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 testcases
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
hide comments
ganeshpc:
20191111 15:26:23
Getting TLE even after precomputation any suggestion??


sanket17:
20190808 13:02:51
precomputation and t*(ba) give tle 

cegprakash:
20190509 21:57:32
author, plz remove spoilers from comments. Encourage others to stop giving away the solution. 

nadstratosfer:
20180109 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 Cstyle 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:
20180107 12:51:23
nice problem :)


dineshvssv:
20171117 06:12:35
Nice problem


saurabh jain:
20160914 23:52:22
nice problem


Govind Lahoti:
20151216 07:11:49
nice problem :) 

Rishabh Joshi:
20150613 21:11:55
Really nice trick to optimize time.


:.Mohib.::
20150611 21:31:14
Just need a better data structure....

Added by:  .:: Pratik ::. 
Date:  20110307 
Time limit:  0.745s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 