Given a positive integer, $N$, the sequence of all fractions $a / b$ with $0 \le a \le b$, $1 \le b \le N$, and $a$ and $b$ relatively prime, listed in increasing order, is called the Farey Sequence of order $N$.
For example, the Farey Sequence of order $6$ is:
If the denominators of the Farey Sequence of order $N$ are:
then the Farey Sum of order $N$ is the sum of $b_ i / b_{i+1}$ from $i = 1 \ldots K-1$.
For example, the Farey Sum of order $6$ is:
Write a program to compute the Farey Sum of order $N$ for a given $N$.
The first line of input contains a single integer $P$ ($1 \le P \le 9\, 999$), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input. It contains the data set number, $K$, followed by the order $N$ ($2 \le N \le 10\, 000$) of the Farey Sum that is to be computed.
For each data set there is a single line of output. The single output line consists of the data set number, $K$, followed by a single space followed by the Farey Sum as a decimal fraction in lowest terms. If the denominator is $1$, print only the numerator.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 6 2 15 3 57 4 9999 |
1 35/2 2 215/2 3 2999/2 4 91180457/2 |