Farey Sequence Length

Given a positive integer N, the sequence of all fractions a/b with (0 ≤ a ≤ b), (1 ≤ b ≤ 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).

Input Specification

The first line of the input contains a single integer P (1 ≤ P ≤ 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 ≤ N ≤ 10 000) of the Farey Sequence whose length is to be found.

Output Specification

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. 4
2. 1 6
3. 2 15
4. 3 57
5. 4 9999

download as text file

Output for Sample Input

1. 1 13
2. 2 73
3. 3 1001
4. 4 30393487

download as text file