시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 65 20 12 28.571%

문제

양의 정수 N에 대해, (0 < a ≤ b), (1 ≤ b ≤ N) 의 조건을 만족하는 모든 기약분수 a/b와 0/1, 1/1을 오름차순으로 나열한 것을 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번째 페리 수열의 분모만을 차례대로 써서 만든 아래와 같은 b 수열이 있다.

b[1], b[2], ..., b[K]

이 때, 페리 수열의 합이란 i = 1부터 K-1까지 b[i]/b[i+1]의 합을 의미한다.

예를 들어, 6번째 페리 수열의 합은 아래와 같다.

1/6 + 6/5 + 5/4 + 4/3 + 3/5 + 5/2 + 2/5 + 5/3 + 3/4 + 4/5 + 5/6 + 6/1 = 35/2

자연수 N에 대해 N번째 페리 수열의 합을 출력하시오.

입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 10000)

각 테스트 케이스는 테스트 케이스의 번호 T와 문제에서 설명한 N의 값이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 10000)

출력

각 테스트 케이스마다 테스트 케이스의 번호와 페리 수열의 합을 출력한다.

합을 출력할 땐 항상 기약분수여야 하며, 합을 기약분수로 나타냈을 때 분모가 1이라면 분자만 출력한다.

예제 입력

4
1 6
2 15
3 57
4 9999

예제 출력

1 35/2
2 215/2
3 2999/2
4 91180457/2

힌트

N+1번째 페리 수열에는 N번째 페리 수열의 모든 분수에 N+1과 서로소인 N 이하의 자연수의 개수만큼의 분수가 추가로 들어간다.