We consider a number to be beautiful if it consists only of the digit repeated one or more times. Not all numbers are beautiful, but we can make any base positive integer beautiful by writing it in another base.
Given an integer , can you find a base (with ) to write it in such that all of its digits become ? If there are multiple bases that satisfy this property, choose the one that maximizes the number of digits.
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case consists of one line with an integer .
输出格式
For each test case, output one line containing Case #x: y, where is the test case number (starting from ) and is the base described in the problem statement.
样例
样例输入 1
2
3
13
样例输出 1
2
3
数据范围与提示
In case #, the optimal solution is to write as in base .
In case #, the optimal solution is to write as in base . Note that we could also write as in base or as in base , but neither of those representations has as many s.
