Time limit: 0.1s
Memory limit: 5MB
Bugland has a mixed population: bugs with antennas and bugs with antennas.
Clearly, the bugs with antennas count in base (they also consider that there are types of bugs in Bugland), and the bugs with antennas count in base .
A number is considered improper if the sum of the digits is different in the eyes of the two species of bugs. In other words, a number is considered improper if the sum of the digits of the number written in base is not the same as the sum of the digits of the number written in base .
In order to promote the equality of the two species of bugs, improper numbers are forbidden.
Considering that the bugs know how to count only from to , how many allowed numbers exist?
The first line will contain the number of scenarios.
The next lines each contain one number , the highest number the bugs know to count to. Please note that the bugs only know positive integer numbers.
The first line will contain numbers, separated by spaces, the number representing the answer to the scenario.
Constraints and clarifications
- For tests worth points: .
- For other tests worth points: .
10 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 2 3 3 3 4
The numbers from to are written in base and base like this:
|base||base||base||the sum in base||the sum in base|
Therefore, the only allowed numbers are: , , , .