Tim has decided to buy some chocolate to (maybe) share with (some of) his friends and family. The shop Tim is going to buy his chocolate from sells it with snap lines moulded in, dividing the block into identical unit squares, and Tim refuses to break the block of chocolate except along an intended snap line. Strangely, however, the shop also refuses to sell more than one row of chocolate at a time, though is willing so sell very long rows, and have a large selection of row lengths on offer. Tim will not share his chocolate unless everyone receiving any chocolate at all receives an equal share, but is uncertain how many people he will be sharing with, and would like to keep his options open. As Tim peruses the cabinet full of chocolate, he finds himself unable to focus, and is struggling to figure out the different ways each row could be shared. Can you help Tim by writing a program to tell him how many different size groups of people he could share with for each row on offer?

Input Specification

The first line will contain an integer \(Q\), the number of rows of chocolate available for purchase. The following \(Q\) lines will each contain a single integer, \(N_i\), the number of pieces of chocolate in the \(i\)th of the \(Q\) rows.

Output Specification

For each row of chocolate specified in the input, and in the same order as given in the input, output a line containing a single integer, the number of different group sizes amongst which that row of chocolate could be shared fairly.

Bounds

Note this problem includes three sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(1 \leq Q, N_i \leq 5000\)
• 20 points: \(1 \leq Q, N_i \leq 100000\)
• 60 points: \(1 \leq Q, N_i \leq 1000000\)

Sample Input

3
1
6
3

Sample Output

1
4
2

Sample Explanation

The rows of chocolate can be shared evenly as follows:

• A row one piece long can only be eaten by one person (probably Tim)
• A row six pieces long can be split fairly in four ways:
  1. One person can have all six pieces
  2. Two people can have three pieces each
  3. Three people can have two pieces each
  4. Six people can have one piece each
• A row three pieces long can be split fairly in two ways:
  1. One person can have all three pieces
  2. Three people can have one piece each