영화 보러 가기

N명의 친구가 함께 동네 극장에 가기로 했다. 모두 같은 줄의 표를 샀다. 영화가 시작하기까지 시간이 조금 남아서, 각자 표를 들고 영화가 시작할 때까지 쇼핑을 하러 갔다.

모두 늦게 돌아왔을 때 영화는 이미 시작한 뒤였다. 입구에 서 있던 안내원은 소녀들을 한 명씩 들여보내기로 했다. 각 소녀는 자기 자리를 찾아 앉아야 한다.

그런데 표를 인쇄하는 기계가 고장 났다. 연속된 번호 대신 각 소녀는 1부터 K 사이의 임의의 좌석 번호를 받았다. 여기서 K는 줄에 있는 좌석 수이다. 받은 좌석 번호가 서로 다르다는 보장은 없다.

소녀가 자리에 앉으려면 좌석 번호 1이 있는 줄 끝에서 들어가 표에 적힌 번호에 이를 때까지 걸어간다. 원하는 좌석이 비어 있으면 그냥 앉는다. 이미 찼다면 같은 방향으로 계속 걸어가 처음으로 나오는 빈 좌석에 앉는다.

자리를 찾지 못하고 줄 끝에 도달하는 불운한 소녀가 생길 수 있다. 이 경우 안내원이 와서 그 소녀를 쫓아낸다.

N과 K가 주어진다.

각 소녀의 표에 적힌 번호는 1 이상 K 이하이며, 각 번호는 균등한 확률로 독립적으로 뽑혔다고 가정한다. 또한 첫 번째 소녀가 자리를 찾기 시작할 때 줄은 완전히 비어 있었다고 가정한다.

안내원에게 쫓겨나는 소녀가 적어도 한 명 있을 확률을 구하라.

첫 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다.

각 테스트 케이스는 정수 N과 K가 주어지는 한 줄로 이루어진다.

각 테스트 케이스마다 확률을 가장 간단한 분수로 한 줄에 출력한다. 분수의 / 기호 앞뒤에는 공백을 출력하지 않는다.

1 ≤ T ≤ 100

세 번째 경우에는 가능한 경우의 수가 $3^3 = 27$이다. 이 중 11가지 경우에 누군가 쫓겨난다. 그 11개의 수열은 133, 222, 223, 232, 233, 313, 322, 323, 331, 332, 333이다.

예를 들어 수열이 322라면 첫 번째 소녀는 3번 좌석에, 두 번째 소녀는 2번 좌석에 앉는다. 세 번째 소녀는 2번 좌석에 가려 하지만 2번과 3번이 모두 차 있는 것을 보고 쫓겨난다.