Under construction

Still being built. Things may change

Spiral Coordinates

Interview

Time limit1sMemory limit128 MB

Summary
Find the (row, column) of N in the clockwise integer spiral centered at 1.
Level

Medium4 of 10

Topics
Math
Solved
No attempts yet

Problem

Lay out the positive integers as shown below. The number 1 sits at the centre and the rest wind outwards clockwise in an infinite spiral.

21  22  23  24  25  26
20   7   8   9  10 ...
19   6   1   2  11 ...
18   5   4   3  12 ...
17  16  15  14  13 ...

Let the centre, the number 1, have position (0,0)(0, 0). Row numbers grow from top to bottom and column numbers grow from left to right, so the number 3 is at (1,1)(1, 1).

Given an integer NN, find the position of the cell that holds it. The answer is a string of the form (R,C), where RR is the row and CC is the column. Neither RR nor CC may carry a leading zero.

Input

The first line contains the number of test cases TT. Each of the next TT lines contains one integer NN (1≤N<2311 \le N < 2^{31}).

Output

For each test case, print the position of NN on its own line in the form (R,C). Put no spaces inside the parentheses, and prefix a negative coordinate with -.

Examples2

  1. Example 1

    Input
    7
2
3
7
17
24
830
765409
    Expected output
    (0,1)
(1,1)
(-1,-1)
(2,-2)
(-2,1)
(-14,3)
(-437,221)

  2. Example 2

    Input
    10
1
2
3
4
5
6
7
8
9
10
    Expected output
    (0,0)
(0,1)
(1,1)
(1,0)
(1,-1)
(0,-1)
(-1,-1)
(-1,0)
(-1,1)
(-1,2)