NSITACMA - Amusing Digits
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.
Added by: | Mukul Gupta |
Date: | 2013-03-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own |