Consider the equation

x² - ny² = 1

where n is some integer.

Find the smallest strictly positive integer solutions (x, y) for a given n.

Input

The number of test cases t (around 30), followed by a list of t values of n (2 ≤ n ≤ 1000). You can assume that the equation can be solved for all values of n in the input set.

Output

For every test case, the values of x and y separated by a space character, on separate lines.

Example

Input:
3
2
6
61

Output:
3 2
5 2
1766319049 226153980