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 representing the number of queries. For each query, you are given an integer You need to find the total number of distinct integers that can be obtained from greatest common divisors (GCDs) of all pair such that is the greater number in the pair and is the smaller number in the pair.
If , then valid pairs will be But and no other pair will be valid as will not be the greater number of the pair.
For example, the total number of pairs is three.
We obtained distinct integers Therefore, for the result is
First line of the testcase contains an integer — indicates number of queries.
Next lines follow, each containing an integer
For each query, print one integer — the answer to the query.
3 1 2 4
0 1 2