This problem is a programming version of Problem 183 from projecteuler.net
Let be a positive integer and let be split into equal parts, , so that .
Let be the product of these parts, .
For example, if is split into five equal parts, , then .
Let for a given value of .
It turns out that the maximum for is found by splitting eleven into four equal parts which leads to ; that is, , which is a terminating decimal.
However, for the maximum is achieved by splitting it into three equal parts, so , which is a non-terminating decimal.
Let if is a non-terminating decimal and if is a terminating decimal.
For example, for is .
Find for .
The first line of each test file contains which is the number of test cases. lines follow, each containing the number for a given test case.
Print exactly lines with a single integer on each line i.e. the answer to the corresponding test.
Sample Input 0
Sample Output 0