Farey Sequence Length

For a positive integer $N$, collect every fraction $a/b$ with $0 \le a \le b \le N$ and $\gcd(a, b) = 1$, then list them from smallest to largest. That list is 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$

Write a program that computes the length of the Farey sequence of order $N$, that is, how many fractions it holds.

The first line contains the number of data sets $P$ ($1 \le P \le 10000$). The data sets are independent of each other and are all processed the same way.

Each of the next $P$ lines holds one data set: the data set number $K$ ($1 \le K \le 10000$) and the order $N$ ($2 \le N \le 10000$) of the Farey sequence whose length is wanted, separated by one space.

Print one line per data set. Each line holds the data set number $K$, one space, and the length of the Farey sequence of order $N$ as a decimal integer.