OpenKattis
Kattis Set 09

#### Start

2019-03-18 13:00 UTC

## Kattis Set 09

#### End

2019-03-25 09:29 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -239 days 21:43:40

164:29:59

0:00:00

# Problem GFarey Sequence Length

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:

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

For this problem, you will write a program to compute the length of the Farey Sequence of order $N$.

## Input

The first line of input contains a single integer $P$ ($1 \le P \le 10\, 000$), 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 Sequence whose length is to be found.

## 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 length of the Farey Sequence as a decimal integer.

Sample Input 1 Sample Output 1
4
1 6
2 15
3 57
4 9999

1 13
2 73
3 1001
4 30393487