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
spoj_mradul: 2020-01-16 16:03:55

getting TLE in python 3.7 but AC in PyPy in 0.18 sec :)

Last edit: 2020-01-16 16:04:25
akhilkumar31e: 2019-10-17 08:22:42

I am getting TLE after I used sieve and precomputation.View my solution and suggest edit.ID:24626264

sid779: 2019-06-30 10:00:31

AC in 3rd go :) read carefully " 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. "

ajkdrag: 2019-06-08 16:45:58

For java submissions, I am getting TLE, even though my code is pretty well optimized - 23895740

selfcoder24: 2019-06-04 10:17:49

Nice problem.
Works with sieve and some precomputation.

uvshuvo: 2018-06-13 20:05:51

very nice problem. thanks

ks1999: 2018-04-20 17:09:25

My 200th on SPOJ.
Enjoyed solving it.

m2do: 2018-03-15 21:27:29

1 is considered non-prime. caused me 4 WAs. finally AC :)

atikahamedutso: 2018-01-28 17:26:50

easy one ac in one go :D
sieve
and precomputing

itachi_2016: 2018-01-04 18:49:02

Awesome question @Piyush. Can you look into my code and suggest some improvements if possible. ID : 20920855.


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