시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 97 32 17 25.000%

문제

양의 정수 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이라면 분자만 출력한다.

예제 입력 1

4
1 6
2 15
3 57
4 9999

예제 출력 1

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

힌트

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

W3sicHJvYmxlbV9pZCI6IjEwNDM4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzk4XHViOWFjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ1NjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTlx1YzVkMCBcdWIzMDBcdWQ1NzQsICgwICZsdDsgYSAmbGU7IGIpLCAoMSAmbGU7IGIgJmxlOyBOKSBcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4IGFcL2JcdWM2NDAgMFwvMSwgMVwvMVx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHVkNTVjIFx1YWM4M1x1Yzc0NCBOXHViYzg4XHVjOWY4IFx1ZDM5OFx1YjlhYyBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA2XHViYzg4XHVjOWY4IFx1ZDM5OFx1YjlhYyBcdWMyMThcdWM1ZjRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGVtPjBcLzEsIDFcLzYsIDFcLzUsIDFcLzQsIDFcLzMsIDJcLzUsIDFcLzIsIDNcLzUsIDJcLzMsIDNcLzQsIDRcLzUsIDVcLzYsIDFcLzE8XC9lbT48XC9wPlxyXG5cclxuPHA+Tlx1YmM4OFx1YzlmOCBcdWQzOThcdWI5YWMgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YmQ4NFx1YmFhOFx1YjljY1x1Yzc0NCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjMzY4XHVjMTFjIFx1YjljY1x1YjRlMCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIGIgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGVtPmJbMV0sIGJbMl0sIC4uLiwgYltLXTxcL2VtPjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1ZDM5OFx1YjlhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTY5XHVjNzc0XHViNzgwIGkgPSAxXHViZDgwXHVkMTMwIEstMVx1YWU0Y1x1YzljMCBiW2ldXC9iW2krMV1cdWM3NTggXHVkNTY5XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNlx1YmM4OFx1YzlmOCBcdWQzOThcdWI5YWMgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48ZW0+MVwvNiArIDZcLzUgKyA1XC80ICsgNFwvMyArIDNcLzUgKyA1XC8yICsgMlwvNSArIDVcLzMgKyAzXC80ICsgNFwvNSArIDVcLzYgKyA2XC8xID0gMzVcLzI8XC9lbT48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjNWYwXHVjMjE4IE5cdWM1ZDAgXHViMzAwXHVkNTc0IE5cdWJjODhcdWM5ZjggXHVkMzk4XHViOWFjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQICZsZTsgMTAwMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4IFRcdWM2NDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBOXHVjNzU4IFx1YWMxMlx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVkMzk4XHViOWFjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTYwIFx1YjU1MCBcdWQ1NmRcdWMwYzEgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHVjNWVjXHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVkNTY5XHVjNzQ0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYzhcdWM3NDQgXHViNTRjIFx1YmQ4NFx1YmFhOFx1YWMwMCAxXHVjNzc0XHViNzdjXHViYTc0IFx1YmQ4NFx1Yzc5MFx1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPk4rMVx1YmM4OFx1YzlmOCBcdWQzOThcdWI5YWMgXHVjMjE4XHVjNWY0XHVjNWQwXHViMjk0IE5cdWJjODhcdWM5ZjggXHVkMzk4XHViOWFjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZDg0XHVjMjE4XHVjNWQwIE4rMVx1YWNmYyBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzggTiBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWJkODRcdWMyMThcdWFjMDAgXHVjZDk0XHVhYzAwXHViODVjIFx1YjRlNFx1YzViNFx1YWMwNFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNDM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmFyZXkgU3VtcyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBwb3NpdGl2ZSBpbnRlZ2VyLCBOLCB0aGUgc2VxdWVuY2Ugb2YgYWxsIGZyYWN0aW9ucyBhXC9iIHdpdGggKDAgJmx0OyBhICZsZTsgYiksICgxICZsZTsgYiAmbGU7IE4pIGFuZCBhIGFuZCBiIHJlbGF0aXZlbHkgcHJpbWUsIGxpc3RlZCBpbiBpbmNyZWFzaW5nIG9yZGVyLCBpcyBjYWxsZWQgdGhlIEZhcmV5IFNlcXVlbmNlIG9mIG9yZGVyIE4uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgRmFyZXkgU2VxdWVuY2Ugb2Ygb3JkZXIgNiBpczo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjBcLzEsIDFcLzYsIDFcLzUsIDFcLzQsIDFcLzMsIDJcLzUsIDFcLzIsIDNcLzUsIDJcLzMsIDNcLzQsIDRcLzUsIDVcLzYsIDFcLzE8XC9wPlxyXG5cclxuPHA+SWYgdGhlIGRlbm9taW5hdG9ycyBvZiB0aGUgRmFyZXkgU2VxdWVuY2Ugb2Ygb3JkZXIgTiBhcmU6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5iWzFdLCBiWzJdLCAuLi4sIGJbS108XC9wPlxyXG5cclxuPHA+dGhlbiB0aGUgRmFyZXkgU3VtIG9mIG9yZGVyIE4gaXMgdGhlIHN1bSBvZiBiW2ldXC9iW2krMV0gZnJvbSBpID0gMSB0byBLLTEuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgRmFyZXkgc3VtIG9mIG9yZGVyIDYgaXM6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4xXC82ICsgNlwvNSArIDVcLzQgKyA0XC8zICsgM1wvNSArIDVcLzIgKyAyXC81ICsgNVwvMyArIDNcLzQgKyA0XC81ICsgNVwvNiArIDZcLzEgPSAzNVwvMjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgRmFyZXkgU3VtIG9mIG9yZGVyIE4gKGlucHV0KS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBzaG91bGQgYmUgcHJvY2Vzc2VkIGlkZW50aWNhbGx5IGFuZCBpbmRlcGVuZGVudGx5LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IHRoZSBvcmRlciBOLCBOICgyICZsZTsgTiAmbGU7IDEwMDAwKSwgb2YgdGhlIEZhcmV5IHN1bSB0aGF0IGlzIHRvIGJlIGNvbXB1dGVkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LiBUaGUgc2luZ2xlIG91dHB1dCBsaW5lIGNvbnNpc3RzIG9mIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGZvbGxvd2VkIGJ5IHRoZSBGYXJleSBTdW0gYXMgYSBkZWNpbWFsIGZyYWN0aW9uIGluIGxvd2VzdCB0ZXJtcy4gSWYgdGhlIGRlbm9taW5hdG9yIGlzIDEsIHByaW50IG9ubHkgdGhlIG51bWVyYXRvci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=