Bags of Candies

There are people who will not be happy solving a problem unless the actual task is hidden behind an elaborate and somewhat unnecessary story. If you are one of those people, this problem is for you.

As an Environment Specialist at a local candy factory, your life is sweet, both figuratively and literally. It is bound to get even sweeter. You were promised a promotion if you can halve the company's plastic footprint, and you plan to do exactly that.

Right now the factory uses huge amounts of plastic packaging. Every day it produces $n$ flavors of candy, numbered from 1 through $n$, and each flavor goes into its own bag. Your idea is to pack two flavors per bag, which halves the number of bags.

It is not that simple. The $i$-th flavor is always produced in quantity $i$, and those $i$ candies are packed into one bag. If flavors $i$ and $j$ share a bag, the candies in that bag must be divided evenly and fairly among a group of friends of some size. Formally, $i$ and $j$ must have a common divisor greater than $1$.

You can pair some flavors into shared bags and put the remaining flavors in their own bags. What is the least number of bags you need?

The first line of input contains the number of test cases $z$ ($1 \le z \le 5$). The descriptions of the test cases follow.

The only line of each test case contains a single number $n$ ($2 \le n \le 10^{11}$), the number of flavors of candy produced at the factory.

For each test case, output a single line containing the least number of bags needed.