"Wow Square" This problem is about the perfect square number, given a positive integer n your task is to find two integers x and y that satisfy:

1) x<y≤n. Remember that x is always less than y.

2) x*y is a perfect square. This means that there's a positive integer z such that z*z=a*b.

3) x*y is maximum. Find x*y as large as possible without violating previous rules.

4*) y-x is maximum. If there still multiple solution x,y that satisfy all previous rules, choose x,y with largest y-x.

Input

First line, there's an integer T(1 ≤ T ≤ 10,000) then T cases follow.

Each test case there's an integer n(4 ≤ n ≤ 10,000,000).

Output

For each test case, output x and y with this fotmat: x*y. see the examples for more detail.

Example

Input:

6

4

10

15

20

321

1020

Output:

1*4

4*9

3*12

8*18

245*320

864*1014

Score is length of your code.

See also: Another problem added 'and recommended (new!)' by Tjandra Satria Gunawan