BCS Mid Wales Programming Contest 2021

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:

(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