18164번 - Count the Bits 서브태스크

작년에 가장 좋아하는 분수를 성공적으로 계산할 수 있었던 키파는 올해 선물로 0과 1이 가득찬 표도 받았겠다 이 수를 이진 전개해 보기로 했습니다.

이진법으로 수를 쭉 적어나가다가 키파는 0보다 1이 훨씬 쓰기 쉽다는 것을 깨달았습니다: 0은 끝을 완벽히 닫아 줘야 하지만, 1은 그럴 필요 없이 쭉 내리기만 하면 되었기 때문입니다!

키파는 이 작업을 질릴 때까지 할 것이기 때문에 이 작업을 무한히 해 나갈 때 쓴 숫자의 개수 중 1의 비율을 최대화하고 싶었습니다. 키파를 위해 이때 1의 비율을 출력하는 프로그램을 작성하세요.

첫 줄에 테스트 케이스의 수 T가 주어집니다.

둘째 줄부터 T개의 줄에 10⁹보다 작거나 같은 두 양의 정수 a, b가 주어집니다. 키파가 이진 전개할 분수가 a/b임을 의미합니다.

T개의 줄에 정답을 기약분수의 형태로 출력합니다. 분자와 분모를 /를 사이에 두고 출력하면 됩니다.

T = 5, b ≤ 10⁶.

T = 5, 모든 분수의 소수 표현의 (이진) 순환마디의 길이의 합이 3·10⁹을 넘지 않음.

T = 10.