Farey Sequence Length

Time limit1sMemory limit256 MB

Summary

Compute 1 plus the sum of Euler totient values up to N for each of up to 10000 data sets.

Level: Medium4 of 10
Topics: Number theory, Prefix sum, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1
1 2
```
Expected output
```
1 3
```

Example 3

Input

Expected output