Count the Bits
시간 제한2초메모리 제한512 MB
각 분수 a/b의 이진 전개에서 1이 차지하는 비율의 최댓값을 구해 기약분수로 출력한다.
문제
작년에 가장 좋아하는 분수를 성공적으로 계산할 수 있었던 키파는 올해 선물로 0과 1이 가득찬 표도 받았겠다 이 수를 이진 전개해 보기로 했습니다.
이진법으로 수를 쭉 적어나가다가 키파는 0보다 1이 훨씬 쓰기 쉽다는 것을 깨달았습니다: 0은 끝을 완벽히 닫아 줘야 하지만, 1은 그럴 필요 없이 쭉 내리기만 하면 되었기 때문입니다!
키파는 이 작업을 질릴 때까지 할 것이기 때문에 이 작업을 무한히 해 나갈 때 쓴 숫자의 개수 중 1의 비율을 최대화하고 싶었습니다. 키파를 위해 이때 1의 비율을 출력하는 프로그램을 작성하세요.
입력
첫 줄에 테스트 케이스의 수 T가 주어집니다.
둘째 줄부터 T개의 줄에 109보다 작거나 같은 두 양의 정수 a, b가 주어집니다. 키파가 이진 전개할 분수가 a/b임을 의미합니다.
출력
T개의 줄에 정답을 기약분수의 형태로 출력합니다. 분자와 분모를 /를 사이에 두고 출력하면 됩니다.