Rational Numbers


In mathematics, a rational number is any number that can be expressed as the quotient or fraction p/q of two integers, with the denominator q not equal to zero. Since q may be equal to 1, every integer is a rational number. Furthermore a set S is called countable if there exists an injective function f from S to the natural numbers N* = {1, 2, 3, ...}.

The set of all real numbers is not countable, but the set of all rational numbers is infinite and countable. In order to prove that let's put all rational numbers in a table with the following rules: in the first row are placed all integer numbers ordered by their absolute value, and placed after each natural number (including zero) its oposite:
0, 1, -1, 2, -2, ..., n, -n, ...,

In the second row all irreducible fractions whose denominator is 2 are placed, ordered by their absolute value and again after each positive number its oposite follows:
1/2, -1/2, 3/2, -3/2, 5/2, -5/2, ...

In general, in the nth row all irreducible fraction with denominator n are placed, ordered by their absolute value and after each positive number its oposite follows. The rational number table that has been obtained possess an infinite number of rows and columns:

Clearly every rational number is placed in the table. Let's enumerate the elements of the table according to the following schematic (arrows indicate the direction of the increasing numeration):

As a result, every rational number receives an unique natural number. Can you tell which rational number occupies the ith position in the table?


There is a single integer T in the first line of input (1 ≤ T ≤ 100). It stands for the number of test cases to follow. Each test case consist of a single line, which contains an integer number i (1 ≤ i ≤ 108).


For each test case print a single line with the ith rational number ri. For ri being an integer number print ri in the usual single integer representation, otherwise (ri is not an integer number) ri must be printed in the format p/q as an irreducible fraction (Greatest Common Divisor of p and q is 1 and q>0). Check the example output for clarification.

Example input:


Example output:


Time and memory limit:

  • 1 seconds
  • 64MB

Problem source: COJ