좌석 배치

어떤 사람들은 회의를 망치는 가장 쉬운 방법은 좌석 배치를 제대로 계획하지 않는 것이라고 믿는다. 회의 의장인 Saanvi는 기조연설 후 열리는 만찬에서 N명의 좌석을 배치하려 하며, 절대적으로 가장 좋은 배치를 고르기 위해 가능한 모든 좌석 배치를 직접 검토하고 싶어 한다. 이것이 가능한지 알아보기 위해, 가능한 좌석 배치의 수를 계산하는 프로그램을 작성하려 한다.

만찬에는 1부터 K까지 번호가 매겨진 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인 경우에는 두 명씩 앉는 테이블 두 개와 한 명이 앉는 테이블 하나가 필요하다. 이 경우 가능한 배치는 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이므로, 5명의 손님이 모두 앉는 테이블 하나만 있다. 이때 답은 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]]

제한

테스트 세트당 시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ K ≤ N.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ T ≤ 36. 1 ≤ N ≤ 8.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ T ≤ 210. 1 ≤ N ≤ 20.

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

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