It's easy to know that arctan(1/2) + arctan(1/3) = arctan(1). Given number A, write a program to calculate the minimum sum B+C. A, B and C are all positive integers and satisfy the equation below:

arctan(1/A) = arctan(1/B) + arctan(1/C)

Input

The first line contains a integer number T (about 1000). T lines follow, each contains a single integer A, 1<=A<=60000.

Output

T lines, each contains a single integer which denotes to the minimum sum B+C.

Example

Sample input:
1
1

Sample output:
5

Added some new test data.