Tyrion Lannister was amused by the interesting properties of digits such as 3 or 9.

If you consider any multiple of 3 and then sum up its digits, the sum is always divisible by 3. For example, 843 is a multiple of 3 and 8 + 4 + 3 = 15 is also multiple of 3. Similarly, for 9, any multiple of 9 satisfies the property that the sum of its digits is also divisible by 9.

But he suddenly realized that this property for 3 or 9 in base 10 may not hold for another base (let say 11).

Inquisitive that he is, he wants to know the number of digits for which this property holds for a particular base non trivially. (For 0 and 1, this property holds trivially and thus can be ignored.)

A base is the number of unique digits, including zero, that is used to represent numbers.

T <= 10000

3 <= N <= 100000

Input

First line contains the number of test cases, T.

Then follows T lines each containing an integer N.

Output

Output consists of T lines. Each line denotes the number of digits for which the property holds in base N.

Example

Input:
3
10
20
3

Output:
2
1
1

Explanation

For base 10, the digits are 3 and 9.

For base 20, the only digit that satisfies the property is 19.