좌석 배치

어떤 사람들은 학회를 망치기 가장 쉬운 방법이 좌석 배치를 잘못 짜는 것이라고 믿는다. 학회 의장 Saanvi는 기조 강연 뒤 이어지는 만찬의 좌석을 계획하고 있다. 참석자는 N명이고, 그녀는 가장 좋은 배치를 고르기 위해 가능한 모든 좌석 배치를 직접 검토하려 한다. 그것이 가능한지 판단하기 위해, 가능한 좌석 배치의 수를 계산하는 프로그램을 작성하려 한다.

만찬에는 K개의 둥근 테이블이 있고, 1번부터 K번까지 번호가 붙어 있다. 각 테이블에 정확히 같은 수의 사람이 앉는 것이 중요하다. 그것이 불가능하면(N이 K로 나누어떨어지지 않으면), 사람이 가장 많은 테이블은 사람이 가장 적은 테이블보다 많아야 한 명 더 앉아 있어야 한다.

N명의 사람은 각각 0과 N - 1 사이의 서로 다른 번호를 받는다. 중요한 것은 누가 누구 옆에 앉는지이고, 정확히 어디에 앉는지는 아니다. 즉, 두 배치 A와 B가 다르다는 것은, 어떤 번호 쌍 α와 β가 있어서 배치 A에서는 α와 β가 같은 테이블에서 서로 옆에 앉아 있지만 배치 B에서는 서로 옆에 앉아 있지 않은 경우를 말한다.

예를 들어 N이 5이고 K가 2이면, 한 테이블에 3명, 다른 테이블에 2명이 앉아야 한다. 다음은 가능한 배치 10가지의 목록이다.

[[0, 1, 2], [3, 4]]
[[0, 1, 3], [2, 4]]
[[0, 1, 4], [2, 3]]
[[0, 2, 3], [1, 4]]
[[0, 2, 4], [1, 3]]
[[0, 3, 4], [1, 2]]
[[1, 2, 3], [0, 4]]
[[1, 2, 4], [0, 3]]
[[1, 3, 4], [0, 2]]
[[2, 3, 4], [0, 1]]

다른 모든 배치는 위 배치 중 하나와 같은 것이며 서로 다른 것으로 세지 않는다. 특히 다음 배치는 모두 같은 것으로 본다.

[[0, 1, 2], [3, 4]]
[[2, 0, 1], [3, 4]]
[[1, 2, 0], [4, 3]]
[[0, 2, 1], [3, 4]]
[[3, 4], [0, 2, 1]]

이 5가지 배치 모두에서 다음 사람 쌍들만 서로 옆에 앉아 있기 때문이다.

0 and 1
0 and 2
1 and 2
3 and 4

또 다른 예로 N = 5, K = 3이면, 2명씩 앉는 테이블 두 개와 1명이 앉는 테이블 하나가 필요하다. 이 경우 가능한 배치는 15가지다.

[[0, 1], [2, 3], [4]]
[[0, 1], [2, 4], [3]]
[[0, 1], [3, 4], [2]]
[[0, 2], [1, 3], [4]]
[[0, 2], [1, 4], [3]]
[[0, 2], [3, 4], [1]]
[[0, 3], [1, 2], [4]]
[[0, 3], [1, 4], [2]]
[[0, 3], [2, 4], [1]]
[[0, 4], [1, 2], [3]]
[[0, 4], [1, 3], [2]]
[[0, 4], [2, 3], [1]]
[[1, 2], [3, 4], [0]]
[[1, 3], [2, 4], [0]]
[[1, 4], [2, 3], [0]]

마지막 예는 N = 5, K = 1로, 테이블이 하나뿐이어서 다섯 명이 모두 그 테이블에 앉는다. 이때 답은 12다.

[[0, 1, 2, 3, 4]]
[[0, 1, 2, 4, 3]]
[[0, 1, 3, 2, 4]]
[[0, 1, 3, 4, 2]]
[[0, 1, 4, 2, 3]]
[[0, 1, 4, 3, 2]]
[[0, 2, 1, 3, 4]]
[[0, 2, 1, 4, 3]]
[[0, 2, 3, 1, 4]]
[[0, 2, 4, 1, 3]]
[[0, 3, 1, 2, 4]]
[[0, 3, 2, 1, 4]]

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개 줄에는 각각 두 정수 N과 K가 주어진다.

각 테스트 케이스마다 "Case #x: y" 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 서로 다른 가능한 좌석 배치의 수다.

• 1 ≤ K ≤ N.