시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 22 16 34.043%

문제

P는 1부터 n까지 수로 이루어진 순열이다. 최대 사이클 1은 P(1), P(P(1)), P(P(P(1))), ... 중 최대값이다.

예를 들어 수열 P가 (3, 2, 5, 4, 1, 7, 8, 6) 이라면

P(1) = 3

P(P(1)) = P(3) = 5

P(P(P(1))) = P(5) = 1

따라서 3, 5, 1이 반복되며, 최대값은 5가 된다.

정수 n(n > 0)과 k(1 <= k <= n)이 주어졌을 때, 최대 사이클 1의 값이 k인 순열의 개수를 구하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 두 개의 정수 n과 k로 이루어져 있다. (1 <= k <= n <= 20)

출력

각 테스트 케이스에 대해서 1, ... n으로 이루어진 순열 중에 최대 사이클 1의 값이 k인 순열의 개수를 출력한다.

예제 입력

4
4 1
7 3
10 5
20 7

예제 출력

6
168
86400
11585247657984000

힌트