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
Praveen Vaka: 2011-07-22 09:35:36

Didn't realize that there could be 20,000 test cases. O(T*(b-a)) would lead to TLE mostly at least mine was with precomputation taking less than 1/10th of a second.

kanishka: 2011-06-24 13:00:13

is thr any need to precompute it....??
i did pre computation plus O(T*(b-a)) and it is giving me tle....any suggestions...

Jay Pandya: 2011-06-23 21:27:58

good one..!!

Suprabh Shukla: 2011-06-22 11:43:03

@Pratik: I think O(T*(b-a)) can still be large enough to tle on the given constraints

Egor: 2011-03-11 00:50:23

be careful with borders!

.:: Pratik ::.: 2011-03-10 14:55:28

Rejudge with a stricter (still very lenient time limit). The original contest was for noobs who didn't know of a very fast method to do IO in Java and hence had higher time limits. Sorry to all, I just saw a O( T*(b-a) ) solution clear.

Jordan Spell: 2011-03-09 19:21:50

Nevermind!

Last edit: 2011-03-09 13:22:20
Knight: 2011-03-09 19:21:50

i think the output for 1 100000 7 is
26318 Plz could u verify once... :-)

Re: Yes you are right sorry... It is a typo.

Last edit: 2011-03-09 19:21:36
.:: Pratik ::.: 2011-03-09 19:21:50

This is a very trivial problem. Should I move to tutorial, or anybody has an idea for challenge? (Lowest source code)

RE(debanjan):We can have this in challenge,if the time limit allows other languages to pass.

Last edit: 2011-03-11 01:03:15

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