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

 

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
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 :)

Ashish Sareen: 2015-03-15 18:27:44

good one... taught me a different approach than standard :-D

ROHAN GULATI: 2014-11-27 03:03:56

Should the bounds (a,b) be included in the answer?

Bharath Reddy: 2014-09-25 05:20:57

A harder variation of this problem: SQFREE


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