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

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

hide comments
2023-03-03 17:54:52
nice problem
2023-02-07 13:15:03
Thanks for the contribution
Can't believe I am getting such well framed exercises to do for free :)
2020-09-11 09:00:18
i am not getting it , anyone knows where to find the solution
2019-11-11 15:26:23
Getting TLE even after precomputation any suggestion??
2019-08-08 13:02:51
precomputation and t*(b-a) give tle
2019-05-09 21:57:32 cegprakash
author, plz remove spoilers from comments. Encourage others to stop giving away the solution.
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.
2018-01-07 12:51:23
nice problem :)
2017-11-17 06:12:35
Nice problem
use prefix array
2016-09-14 23:52:22 saurabh jain
nice problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.