VECTAR8  Primal Fear
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:
20170911 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


nihal_magdy:
20170818 11:48:23
@piyush can you see what is the wrong test i get with my code 19995055 

rohit659:
20170406 21:42:37
NICE PROBLEM !!!


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

rainy jain :
20160913 02:32:57


sy_117:
20160813 15:33:29
such a nice problem !!! A lot of optimization needed to avoid TLE . :) 

crazy97:
20160725 20:53:11
Last edit: 20160730 08:44:42 

sachintanwar:
20160708 09:30:46
@Piyush


sumit kumar singh:
20160707 11:44:03
cin/cout caused me 2 TLE .. :(


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

Added by:  Piyush Kumar 
Date:  20160704 
Time limit:  0.300s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 