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
|
yefricruz_02:
2023-01-12 23:50:56
Thanks @shokal_kishan, I missed to delete all digits which they love, |
|
shokal_kishan:
2022-07-06 14:43:20
test cases
|
|
fjkexgnffhwihp:
2022-06-22 14:23:30
I think I precalculated all the "scary primes" correctly, but I'm getting WAs. Can anyone provide any test cases? |
|
dhaka_1436:
2022-04-18 10:52:55
Can You Please provide any test cases? i am unable to figure out the error in my code |
|
manjotkaur__09:
2021-07-28 12:49:33
read the question statement carefully,hint is in the question statement itself |
|
sachin_08:
2021-06-09 20:34:00
try ios_base::sync_with_stdio(false);cin.tie(NULL);
|
|
rrdesh_07:
2021-01-26 11:52:29
i am also getting tle ,even though i have used sieve and it runs very well on desktop compiler .
|
|
omkarg_1417:
2020-09-15 18:58:44
By precomputation I thought just to do seive before input, but it was everything to be done in this problem before input :) |
|
ashutosh_aswal:
2020-07-18 08:34:10
All comments are just Ac in this much, Ac in that much.
|
|
atom_jojo:
2020-07-11 09:31:20
AC in 0.02 sec using sieve and precalculation in cpp |
| 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 |
RSS