페리 수열의 길이

양의 정수 $N$에 대해 $0 \le a \le b \le N$이고 $\gcd(a, b) = 1$인 분수 $a/b$를 모두 모아 작은 값부터 차례로 나열한 것을 차수 $N$의 페리 수열이라고 한다.

예를 들어 차수 6의 페리 수열은 다음과 같다.

$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$의 페리 수열의 길이, 즉 그 안에 들어 있는 분수의 개수를 구하는 프로그램을 작성한다.

첫째 줄에 데이터 집합의 개수 $P$ ($1 \le P \le 10000$)가 주어진다. 각 데이터 집합은 서로 독립이고 처리 방법은 모두 같다.

다음 $P$개의 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄에는 데이터 집합 번호 $K$ ($1 \le K \le 10000$)와 길이를 구할 페리 수열의 차수 $N$ ($2 \le N \le 10000$)이 공백 하나로 구분되어 주어진다.

데이터 집합마다 한 줄씩 출력한다. 각 줄에는 데이터 집합 번호 $K$, 공백 하나, 차수 $N$의 페리 수열의 길이를 십진 정수로 이어서 출력한다.