InternDoor

How many numbers divide it

Mediummath · number theoryRead the input, print the output

Reported in interviews at (where)

For each number n, count the whole numbers from 1 to n that divide n exactly, with nothing left over. 1 and n itself always count.

Checking every number up to n is far too slow for the largest tests: think about the divisors in pairs.

Input

The first line holds T, the number of tests. Each test is one line holding one whole number n.

Output

For each test, one line: how many whole numbers divide its n exactly.

Example
Input
4
12
1
36
97
Output
6
1
9
2
  1. 1, 2, 3, 4, 6 and 12.
  2. Only 1 itself.
  3. 1, 2, 3, 4, 6, 9, 12, 18 and 36: 6 pairs with itself, so it counts once.
  4. 97 is prime: only 1 and 97.

Limits

  • 1 <= T <= 200
  • 1 <= n <= 1000000000

Hints

Hint 1

If d divides n, so does n / d, and one of the two is at most the square root of n.

Hint 2

Count each pair d and n / d with d * d <= n twice, unless d * d == n.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.