Expectation

Eric built a simple scheme for generating random integers. Given an integer $n$, it outputs a uniformly random integer between $0$ and $n-1$ inclusive. For example, when $n = 3$ it returns $0$, $1$, or $2$, each with probability $1/3$.

Eric now wants a more elaborate scheme. He takes two independent copies of this generator and feeds their outputs into a bitwise XOR gate, which returns the bitwise exclusive or of its two inputs. His friend Nick is curious about the expectation of the result, and they would like you to compute it.

Recall that the expectation of a random variable is its average value. For a variable $\xi$ taking non-negative integer values it is

$\mathbf{E}[\xi] = \sum_{i=0}^{\infty} i \cdot p_i$

where $p_i$ is the probability that $\xi$ equals $i$.

The exact expectation is always a rational number, so you must report it exactly rather than as a rounded decimal.

The first line contains the number of test cases $k$ ($1 \le k \le 1000$). Each of the next $k$ lines contains a single integer $n$ ($1 \le n \le 10^9$).

For each test case, output the exact expected value of the XOR of the two generators' outputs as an irreducible fraction $p/q$, where $q \ge 1$ and $\gcd(p, q) = 1$. If the value is an integer, still write it with denominator $1$ (for example, $0/1$). Print the answer for each test case on its own line.