Farey 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:

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

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.

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 |