Project Euler #187: Semiprimes

_{This problem is a programming version of Problem 187 from projecteuler.net}

A composite is a number containing at least two prime factors. For example, ; ; .

There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: , , , , , , , , , .

How many composite integers , , have precisely two, not necessarily distinct, prime factors?

Input Format

The first line of each test file contains a single integer , the number of test cases. lines follow, each containing a single integer .

Constraints

Output Format

Output exactly lines with a single number on each - an answer to the corresponding test case.

Sample Input

1
5

Sample Output