Q-Primes

0

0 votes
Prime Factorization, Number theory
Problem

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

1T100

0N106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For N = 15, the only 4 Q-Prime numbers are 6, 10, 14 and 15

Editor Image

?