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
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....


kartikay singh:
20150603 12:44:02
Nice problem (y) 

Sahil Sharma:
20150515 16:16:17
Weird thing just happened. Same solution gets AC in c++4.3 and gets Seg fault in c++ 4.9 :O Anyone knows why? 

karan:
20150422 13:58:57
nice problem :) 

Ashish Sareen:
20150315 18:27:44
good one... taught me a different approach than standard :D 

ROHAN GULATI:
20141127 03:03:56
Should the bounds (a,b) be included in the answer? 

Bharath Reddy:
20140925 05:20:57
A harder variation of this problem: SQFREE 
Added by:  .:: Pratik ::. 
Date:  20110307 
Time limit:  0.745s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 