We know that prime numbers are numbers that are divisible by only 1 and the number themselves. Formally, they have only two positive divisors. Let us define a new set of numbers called Q-Primes that have only four positive divisors.
Given a number N, your task is to find the number of Q-Prime numbers up to N. You have to do this for T test cases.
Input Format:-
The first lines contains one integer T, denoting the number of test cases.
Each of the T following lines contains one integer each, i.e., N
Output Format:-
For each test case, print only one integer denoting the number of Q-Prime numbers up to N.
Constraints
1≤T≤100
0≤N≤106
For N = 15, the only 4 Q-Prime numbers are 6, 10, 14 and 15