VECTAR8 - Primal Fear

no tags 

Changu and Mangu are afraid of prime numbers, but they are not afraid of all prime numbers. They were afraid of only a special kind of prime numbers. They are afraid of the prime numbers (without the digit zero, they love all the primes which have digits 0 in them) that remain prime no matter how many of the leading digits are omitted. For example, they are afraid of 4632647 because it doesn't have the digit 0 and each of its truncations (632647, 32647, 2647, 647, 47, and 7) are primes.

You are given a simple task, given a number of N, find out the number of primes not greater that N, that changu and mangu are afraid of.

Input

The first line contains T, the number of test cases. T lines follow, each containing a number N.

Output

On each line print the number of primes not greater that N, that changu and mangu are afraid of.

Example

Input:
3
2
3
4

Output:
1
2
2

Constraints

T ≤ 10^5

1 ≤ N < 10^6


hide comments
omarwageeh: 2017-09-11 09:58:19

make sure you check that all the truncations of a prime that has no zeroes are prime as in the example.... 632647, 32647, 2647, 647, 47, and 7
Caused me 3 WA

nihal_magdy: 2017-08-18 11:48:23

@piyush can you see what is the wrong test i get with my code 19995055

rohit659: 2017-04-06 21:42:37

NICE PROBLEM !!!
AC IN ONE GO!!!

dwij28: 2016-10-07 23:40:01

A very nice problem. In fact all problems by @Piyush Kumar i.e the VECTAR series are very nice. :)

rainy jain : 2016-09-13 02:32:57


Last edit: 2016-09-13 09:21:17
sy_117: 2016-08-13 15:33:29

such a nice problem !!! A lot of optimization needed to avoid TLE . :)

crazy97: 2016-07-25 20:53:11

Last edit: 2016-07-30 08:44:42
sachintanwar: 2016-07-08 09:30:46

@Piyush
I used this code and getting TLE continuously
<code deleted>

Re: Please don't post any codes here. Use Forum.
Brute Force won't pass. Think of other ways. Good luck.

Last edit: 2016-07-08 16:27:57
sumit kumar singh: 2016-07-07 11:44:03

cin/cout caused me 2 TLE .. :(

Re: cin/cout will not cause you TLE if you have an efficient solution. My slowest solution uses cin/cout and passes the time limit comfortably.

Last edit: 2016-07-07 12:33:56
akshayvenkat: 2016-07-07 08:26:26

@piyush please check my submission. is this way of solving ethically acceptable? ID:17236762

Re: Yeah, you can do this any time :) But for a challenge, you can try out other ways :)!

Last edit: 2016-07-07 08:57:53

Added by:Piyush Kumar
Date:2016-07-04
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY