【 2017"百度之星"程式設計大賽 - 初賽（A）1001小C的倍數問題】

【連結】：http://acm.hdu.edu.cn/showproblem.php?pid=6108

【題目】：

小C的倍數問題

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 362    Accepted Submission(s): 201

Problem Description

根據國小數學的知識，我們知道一個正整數x是3的倍數的條件是x每一位加起來的和是3的倍數。反之，如果一個數每一位加起來是3的倍數，則這個數肯定是3的倍數。

現在給定進制P，求有多少個B滿足P進制下，一個正整數是B的倍數的充分必要條件是每一位加起來的和是B的倍數。

Input

第一行一個正整數T表示資料組數(1<=T<=20)。

接下來T行，每行一個正整數P(2 < P < 1e9)，表示一組詢問。

Output

對于每組資料輸出一行，每一行一個數表示答案。

Sample Input

1

10

Sample Output

3

Source

​​2017"百度之星"程式設計大賽 - 初賽（A）​​