Limits 1.5s, 64 MB

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,Q, representing the number of queries. For each query, you are given an integer X.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)(i, X) such that XX is the greater number in the pair and i(1i<X)i (1≤i<X) is the smaller number in the pair.

More formally,

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

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

  • gcd(1,4)=1gcd(1, 4) = 1

  • gcd(2,4)=2gcd(2, 4) = 2

  • gcd(3,4)=1gcd(3, 4) = 1

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


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

Next QQ lines follow, each containing an integer X.X.




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




Login to submit.


65% Solution Ratio
Asif_AlimEarliest, 6M ago
IU_SpiralForgeFastest, 0.2s
user.434849Lightest, 4.9 MB
user.6612Shortest, 732B
Toph uses cookies. By continuing you agree to our Cookie Policy.