Hide

Problem B
Farey Sums

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:

$\frac{0}{1}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{1}{1} $

If the denominators of the Farey Sequence of order $N$ are:

$b_1, b_2, \ldots , b_ K$

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:

$\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} $

Write a program to compute the Farey Sum of order $N$ for a given $N$.

Input

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.

Output

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
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Source 2014 Greater New York Region ACM Regional Contest
License For educational use only

Please log in to submit a solution to this problem

Log in