1의 최대 사이클 값

P는 1부터 n까지의 정수를 한 번씩 포함하는 순열이다. 1에서 시작해 P를 반복해서 적용하면 다음과 같은 수열이 생긴다.

P(1), P(P(1)), P(P(P(1))), ...

이 반복되는 사이클에 나타나는 값들 중 최댓값을 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이 반복되고, 1의 최대 사이클 값은 5이다.

정수 n과 k가 주어질 때, 1의 최대 사이클 값이 정확히 k인 순열의 개수를 구하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 1,000)

각 테스트 케이스는 두 정수 n과 k로 이루어진다. (1 <= k <= n <= 20)

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