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

hide comments
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!

:.Mohib.:: 2015-06-11 21:31:14

Just need a better data structure....
Ac in one go ;)

kartikay singh: 2015-06-03 12:44:02

Nice problem (y)

Sahil Sharma: 2015-05-15 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: 2015-04-22 13:58:57

nice problem :)


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