WOW_SQR - Wow Square

"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<yn. 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


Added by:Tjandra Satria Gunawan
Date:2012-12-14
Time limit:1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2013-06-05 19:14:08 Ouditchya Sinha
Use long long. :)
2013-04-29 16:32:39 VV
Can't seem to find anything better than O(sqrt(n)) so that I can use anything other than C :(
2012-12-22 06:51:15 Aditya Pande
Edit:
it is Mitch yet again

Last edit: 2013-06-23 06:00:31
2012-12-18 05:31:44 Aditya Pande
got Accpeted in 0.00
best c solution so far



Last edit: 2013-01-21 09:57:52
2012-12-14 19:00:42 XeRoN!X
Consider moving it to classical section because there are already lot of shortening problems OR add some more interesting constraints and scoring.
Ans: I think this problem is too easy for classical so I moved it to challenge... Ok, next time I'll post challenge problem with my own judge/scoring system ;-)

Last edit: 2012-12-14 21:00:03
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.