시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 96 31 16 23.881%

문제

양의 정수 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+XHJcblxyXG48cD5cdWM3NzQgXHViNTRjLCBcdWQzOThcdWI5YWMgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1Yjc4MCBpID0gMVx1YmQ4MFx1ZDEzMCBLLTFcdWFlNGNcdWM5YzAgYltpXVwvYltpKzFdXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDZcdWJjODhcdWM5ZjggXHVkMzk4XHViOWFjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGVtPjFcLzYgKyA2XC81ICsgNVwvNCArIDRcLzMgKyAzXC81ICsgNVwvMiArIDJcLzUgKyA1XC8zICsgM1wvNCArIDRcLzUgKyA1XC82ICsgNlwvMSA9IDM1XC8yPFwvZW0+PFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNWQwIFx1YjMwMFx1ZDU3NCBOXHViYzg4XHVjOWY4IFx1ZDM5OFx1YjlhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUCAmbGU7IDEwMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOCBUXHVjNjQwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgTlx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDM5OFx1YjlhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2MCBcdWI1NTAgXHVkNTZkXHVjMGMxIFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1YzVlY1x1YzU3YyBcdWQ1NThcdWJhNzAsIFx1ZDU2OVx1Yzc0NCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGM4XHVjNzQ0IFx1YjU0YyBcdWJkODRcdWJhYThcdWFjMDAgMVx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWJkODRcdWM3OTBcdWI5Y2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5OKzFcdWJjODhcdWM5ZjggXHVkMzk4XHViOWFjIFx1YzIxOFx1YzVmNFx1YzVkMFx1YjI5NCBOXHViYzg4XHVjOWY4IFx1ZDM5OFx1YjlhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHViYWE4XHViNGUwIFx1YmQ4NFx1YzIxOFx1YzVkMCBOKzFcdWFjZmMgXHVjMTFjXHViODVjXHVjMThjXHVjNzc4IE4gXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5Y2NcdWQwN2NcdWM3NTggXHViZDg0XHVjMjE4XHVhYzAwIFx1Y2Q5NFx1YWMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQzOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhcmV5IFN1bXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciwgTiwgdGhlIHNlcXVlbmNlIG9mIGFsbCBmcmFjdGlvbnMgYVwvYiB3aXRoICgwICZsdDsgYSAmbGU7IGIpLCAoMSAmbGU7IGIgJmxlOyBOKSBhbmQgYSBhbmQgYiByZWxhdGl2ZWx5IHByaW1lLCBsaXN0ZWQgaW4gaW5jcmVhc2luZyBvcmRlciwgaXMgY2FsbGVkIHRoZSBGYXJleSBTZXF1ZW5jZSBvZiBvcmRlciBOLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIEZhcmV5IFNlcXVlbmNlIG9mIG9yZGVyIDYgaXM6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4wXC8xLCAxXC82LCAxXC81LCAxXC80LCAxXC8zLCAyXC81LCAxXC8yLCAzXC81LCAyXC8zLCAzXC80LCA0XC81LCA1XC82LCAxXC8xPFwvcD5cclxuXHJcbjxwPklmIHRoZSBkZW5vbWluYXRvcnMgb2YgdGhlIEZhcmV5IFNlcXVlbmNlIG9mIG9yZGVyIE4gYXJlOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+YlsxXSwgYlsyXSwgLi4uLCBiW0tdPFwvcD5cclxuXHJcbjxwPnRoZW4gdGhlIEZhcmV5IFN1bSBvZiBvcmRlciBOIGlzIHRoZSBzdW0gb2YgYltpXVwvYltpKzFdIGZyb20gaSA9IDEgdG8gSy0xLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIEZhcmV5IHN1bSBvZiBvcmRlciA2IGlzOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+MVwvNiArIDZcLzUgKyA1XC80ICsgNFwvMyArIDNcLzUgKyA1XC8yICsgMlwvNSArIDVcLzMgKyAzXC80ICsgNFwvNSArIDVcLzYgKyA2XC8xID0gMzVcLzI8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIEZhcmV5IFN1bSBvZiBvcmRlciBOIChpbnB1dCkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgc2hvdWxkIGJlIHByb2Nlc3NlZCBpZGVudGljYWxseSBhbmQgaW5kZXBlbmRlbnRseS48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIG9mIGlucHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSB0aGUgb3JkZXIgTiwgTiAoMiAmbGU7IE4gJmxlOyAxMDAwMCksIG9mIHRoZSBGYXJleSBzdW0gdGhhdCBpcyB0byBiZSBjb21wdXRlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBhIHNpbmdsZSBsaW5lIG9mIG91dHB1dC4gVGhlIHNpbmdsZSBvdXRwdXQgbGluZSBjb25zaXN0cyBvZiB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSBmb2xsb3dlZCBieSB0aGUgRmFyZXkgU3VtIGFzIGEgZGVjaW1hbCBmcmFjdGlvbiBpbiBsb3dlc3QgdGVybXMuIElmIHRoZSBkZW5vbWluYXRvciBpcyAxLCBwcmludCBvbmx5IHRoZSBudW1lcmF0b3IuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d