Farey Sequence Sum

For a positive integer $N$, take every irreducible fraction $a/b$ with $0 < a \le b$ and $1 \le b \le N$, together with $0/1$ and $1/1$, and sort them in increasing order. The result is the $N$-th Farey sequence.

For example, the 6th Farey sequence is:

$0/1,\ 1/6,\ 1/5,\ 1/4,\ 1/3,\ 2/5,\ 1/2,\ 3/5,\ 2/3,\ 3/4,\ 4/5,\ 5/6,\ 1/1$

Writing down only the denominators of the $N$-th Farey sequence, in order, gives a sequence $b_1, b_2, \dots, b_K$ of length $K$. The Farey sum is the total of $b_i / b_{i+1}$ over $i = 1$ through $K-1$.

$\sum_{i=1}^{K-1} \frac{b_i}{b_{i+1}}$

The sum for the 6th Farey sequence works out like this:

$\frac{1}{6} + \frac{6}{5} + \frac{5}{4} + \frac{4}{3} + \frac{3}{5} + \frac{5}{2} + \frac{2}{5} + \frac{5}{3} + \frac{3}{4} + \frac{4}{5} + \frac{5}{6} + \frac{6}{1} = \frac{35}{2}$

Given $N$, compute the sum of the $N$-th Farey sequence.

The first line holds the number of test cases $P$. ($1 \le P \le 10000$)

Each of the next $P$ lines holds a test case number $T$ and the value $N$ described above, separated by one space. ($1 \le T \le 10000$, $2 \le N \le 10000$)

For each test case, print the test case number given in the input and the Farey sum on one line, separated by one space. Reprint the number exactly as it appears in the input, and keep the lines in input order.

Always write the sum as a reduced fraction in the form numerator/denominator. If the reduced denominator is 1, print only the numerator.

The $(N+1)$-th Farey sequence contains every fraction of the $N$-th one, plus as many new fractions as there are positive integers up to $N$ that are coprime with $N+1$.