SPOJ CANTON

Summary

Given a number n, find it's corresponding term in Cantor's enumeration.

Explanation

This problem breaks down into two steps:

• 1) Find the diagonal for the given number.
• 2) Find the value of the endpoint of the found diagonal.

The first part is relatively straightforward. The length of each diagonal grows in a Triangular Series, therefore; ${\displaystyle n={\frac {\sqrt {8x+1}}{2}}}$ where ${\displaystyle x}$ is the given number and ${\displaystyle n}$ is the diagonal. Next, the endpoint of the diagonal is given by; ${\displaystyle T_{n}={\frac {n^{2}+n}{2}}}$. Now, the difference from the given number and the endpoint can be found. Counting this difference from the lower left for odd numbered diagonals or the upper right for even numbered diagonals will yield the required term.

Implementation

Care must be taken with the integer division rounding. A function that takes this into account might look like this:

int FindDiagonal(int n)
{
return (sqrt(8*n+1))/2;
}


Input

The first line contains the number of test cases ${\displaystyle T\leq 20}$. The next T lines each contain a number ${\displaystyle 1\leq n\leq 10^{7}}$ for which to find the associated term.

5
3
14
7
10000000
25


Output

Note that the extra verbiage is required.

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629
TERM 25 IS 4/4