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.