Efa loves numbers. She thinks a number is powerful if it can be expressed in the form where and are both positive integers greater than . For example, and are powerful as we can express as and as , but and are not.
You are given a number . Find the minimum positive integer such that is powerful.
The first line contains a single integer the number of test cases.
Each test case consists of one line containing the integer .
For each test case, print one integer in a single line.
Input | Output |
---|---|
5 1 16 116 7936 1935360 | 4 1 29 31 210 |