A number is said to be prime number if it is has only 2 distinct positive divisors. But, Ser is quite creative. He invents another type of number called Ser-Prime that has 5 distinct positive divisors.

Given an integer N, it is the duty of Ser's disciples to find the number of Ser-Primes less than or equal to N. 

Input Format

The first line consists of a number T representing the number of Test Cases.

Then T lines follow, Each line consists of a number N representing the input for that test case.

Output Format

Print a single integer for each test case- the number of Ser-Primes less than or equal to N.

Print answers for different test cases in different lines.

Constraints

$1<=N<= 10 ^ {18}$

$1<=T<= 10^5$