FCTORISE - Factorising odd numbers

Any odd integer, m, greater than 1, can be factorised by expressing it as the difference of two squares, since if m = x^2 - y^2 then m = (x+y)*(x-y), so m has factors x+y and x-y.

For example, 15 = 4^2 - 1^2 = (4+1)*(4-1) = 5*3.

Rearranging the first equation above gives m + y^2 = x^2, so we can find x and y by evaluating m + y^2 for y = 0, 1, 2 ... until the perfect square x^2 is found.

Write a program to factorise an odd integer greater than 1 by expressing it as the difference of two squares.

Input

The first line of the input is the number of cases (a positive integer, n, on one line).

This is followed by n odd integers greater than 1, each on a line of its own.

Output

The output should consist of:

m = x^2 - y^2 = (x+y)*(x-y)

(with the actual values for m, x, and y).

Example

Input:
2
15
9929

Output:
15 = 4^2 - 1^2 = 5*3
9929 = 4965^2 - 4964^2 = 9929*1

Added by:handee
Date:2021-06-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-07-04 23:05:31
Output x, y found first using the method described in the statement, eg. 15 = 8^2 - 7^2 = 15*1 is not an accepted answer.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.