숲의 현상
시간 제한2초메모리 제한256 MB
n 곱하기 m 격자의 각 칸이 이웃한 칸 하나를 균등한 확률로 골라 장작을 보낼 때, 장작을 한 개 이상 받는 칸 수의 기댓값을 구한다.
문제
바이트란디아는 숲과 강, 호수가 많은 매우 푸르고 친환경적인 나라이다. 바이트란디아의 모든 숲은 완벽한 직사각형 모양이다. i번째 숲의 변의 길이는 ni킬로미터와 mi킬로미터이다. 각 숲은 직사각형의 변에 평행한 선으로 나뉘어 한 변의 길이가 1킬로미터인 정사각형들이 된다. 각 정사각형에는 산림 관리인이 한 명씩 산다.
알려진 대로, 가을이 되면 모든 산림 관리인은 겨울을 날 땔감을 준비한다. 그런데 이번 가을에 상상할 수 없는 일이 일어났다. 아무도 모르는 이유로, 땔감을 준비한 뒤 모든 산림 관리인은 자신의 목재 비축량 전부를 무작위로, 같은 확률로 선택된 이웃에게 무료로 보냈다. 모든 산림 관리인은 동시에 목재를 보냈다. 두 산림 관리인이 이웃이라는 것은 그들이 사는 정사각형이 한 변을 공유한다는 뜻이다.
이 인간 행동의 현상을 더 자세히 연구하기 위해, 각 숲마다 이 과정 후에 겨울을 날 땔감을 조금이라도 가지게 된 산림 관리인 수의 기댓값을 구해야 한다.
입력
첫 번째 줄에는 바이트란디아의 숲 수 t가 주어진다.
다음 t개 줄 각각에는 i번째 숲의 변의 길이 ni와 mi가 주어진다. (1 ≤ ni ≤ 10^7, 1 ≤ mi ≤ 10^7, ni·mi ≥ 2)
바이트란디아의 숲 수는 10000을 넘지 않는다.
출력
각 숲마다 한 줄에 구하는 기댓값을 기약분수 형태로 출력한다. 분자와 분모는 추가 공백 없이 / 기호로 구분한다. 분모가 1이면 분자만 출력한다.