Battle With GCD

Once upon a time, in a bustling metropolis, Ava, a brilliant AI researcher, was dedicated to creating an AI system that could revolutionize human interactions and emotional well-being. After years of tireless work, she finally achieved a breakthrough—she developed an advanced AI named Serena, designed to be a sentient companion capable of understanding and empathizing with human emotions. One day, a resident named Mr. Thompson, a grumpy and withdrawn elderly man, reluctantly interacted with Serena. Over time, he realized that Serena was different from the others—he could see the genuine care and understanding in her eyes. Serena's unwavering compassion slowly broke through Mr. Thompson's tough exterior, and he shared stories about his past and the pain he carried deep within.

Now, As a problem solver, you prefer to share a problem with Serena rather than delve into your past or personal experiences. However, before sharing the problem with Serena, you will solve it yourself so that you can confidently answer any counter questions she may have. You want to avoid a situation where you cannot answer, leading Serena to laugh at you.

You are given an integer $Q,$ representing the number of queries. For each query, you are given an integer $X.$ You need to find the total number of distinct integers that can be obtained from greatest common divisors (GCDs) of all pair $(i, X)$ such that $X$ is the greater number in the pair and $i (1≤i<X)$ is the smaller number in the pair.

More formally,

If $X=4$, then valid pairs will be $(1, 4),(2,4),(3,4).$ But $(4, 5),(4, 4),(2, 3)…$ and no other pair will be valid as $X$ will not be the greater number of the pair.

For example, $X = 4,$ the total number of pairs is three.

• $gcd(1, 4) = 1$

• $gcd(2, 4) = 2$

• $gcd(3, 4) = 1$

We obtained $2$ distinct integers $[1, 2].$ Therefore, for $X = 4,$ the result is $2.$

Input

First line of the testcase contains an integer $Q$ — indicates number of queries.

Next $Q$ lines follow, each containing an integer $X.$

$1≤Q≤10^4$

$1≤X≤10^{10}$

Output

For each query, print one integer — the answer to the query.

Sample

Input	Output
3 1 2 4	0 1 2