给定一个正整数 $N$，所有满足 $0 < a \le b$，$1 < b \le N$，且 $a$ 与 $b$ 互质的分数 $a / b$ 按升序排列组成的序列，被称为 $N$ 阶 Farey 序列（Farey Sequence of order $N$）。

例如，6 阶 Farey 序列为： $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$

对于本题，你需要编写一个程序来计算 $N$ 阶 Farey 序列的长度。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 10000$)，表示随后数据组的数量。每组数据应被独立处理。

每组数据占一行，包含数据编号 $K$，以及需要计算其 Farey 序列长度的阶数 $N$ ($2 \le N \le 10000$)。

输出格式

对于每组数据，输出一行。输出行包含数据编号 $K$，后跟一个空格，再跟该 Farey 序列的长度（十进制整数）。

样例

样例输入 1

4
1 6
2 15
3 57
4 9999

样例输出 1

1 13
2 73
3 1001
4 30393487