Problem G
Snack Prep

Grace is preparing for a long and difficult hike. She has a large bag of trail mix that weighs $G$ grams. Grace wants to share the snacks with her friends, but she doesn’t know how many people will join her. To be prepared, she decides to figure out all the possible ways to split the trail mix into smaller bags so that each bag has the same integer number of grams. Since there is a possibility that no friends will join Grace, placing all the trail mix into one bag is a valid way to split the trail mix.

How many different ways can Grace split her trail mix bags?

Input

The first line of input contains a single integer $N$ $(1 \leq N \leq 10)$ the number of test cases. The next $N$ lines will contain a single integer $G$ $(1 \leq G \leq 10^{18})$ the weight of Grace’s trail mix bag.

Output

Print $N$ lines, one for each test case. Each line should contain the number of ways Grace can split her trail mix bag such that each smaller bag weighs the same.

3
2
4
8

2
3
4

3
7
17
23

2
2
2

1
123456789

12