시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 63 26 18 36.735%

문제

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인 순열의 개수를 출력한다.

예제 입력 1

4
4 1
7 3
10 5
20 7

예제 출력 1

6
168
86400
11585247657984000
W3sicHJvYmxlbV9pZCI6IjI2ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDAgXHVjMGFjXHVjNzc0XHVkMDc0IDEiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0XHVjNzc0XHViMmU0LiBcdWNkNWNcdWIzMDAgXHVjMGFjXHVjNzc0XHVkMDc0IDFcdWM3NDAgUCgxKSwgUChQKDEpKSwgUChQKFAoMSkpKSwgLi4uIFx1YzkxMSBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjMjE4XHVjNWY0IFBcdWFjMDAgKDMsIDIsIDUsIDQsIDEsIDcsIDgsIDYpIFx1Yzc3NFx1Yjc3Y1x1YmE3NDxcL3A+XHJcbjxwPlxyXG5cdFAoMSkgPSAzPFwvcD5cclxuPHA+XHJcblx0UChQKDEpKSA9IFAoMykgPSA1PFwvcD5cclxuPHA+XHJcblx0UChQKFAoMSkpKSA9IFAoNSkgPSAxPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjUzMFx1Yjc3Y1x1YzExYyAzLCA1LCAxXHVjNzc0IFx1YmMxOFx1YmNmNVx1YjQxOFx1YmE3MCwgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQwIDVcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MTVcdWMyMTggbihuICZndDsgMClcdWFjZmMgaygxICZsdDs9IGsgJmx0Oz0gbilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwIFx1YzBhY1x1Yzc3NFx1ZDA3NCAxXHVjNzU4IFx1YWMxMlx1Yzc3NCBrXHVjNzc4IFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmx0Oz0gVCAmbHQ7PSAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVhY2ZjIGtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDEgJmx0Oz0gayAmbHQ7PSBuICZsdDs9IDIwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAxLCAuLi4gblx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0IFx1YzkxMVx1YzVkMCBcdWNkNWNcdWIzMDAgXHVjMGFjXHVjNzc0XHVkMDc0IDFcdWM3NTggXHVhYzEyXHVjNzc0IGtcdWM3NzggXHVjMjFjXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjgyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWF4aW11bSBpbiB0aGUgQ3ljbGUgb2YgMSIsImRlc2NyaXB0aW9uIjoiPHA+SWYgUCBpcyBhIHBlcm11dGF0aW9uIG9mIHRoZSBpbnRlZ2VycyAxLC4uLiwgbiwgdGhlIG1heGltdW0gaW4gdGhlIGN5Y2xlIG9mIDEgaXMgdGhlIG1heGltdW0gb2YgdGhlIHZhbHVlcyBQKDEpLCBQKFAoMSkpLCBQKFAoUCgxKSkpLCBldGMuIEZvciBleGFtcGxlLCBpZiBQIGlzIHRoZSBwZXJtdXRhdGlvbjo8XC9wPlxyXG5cclxuPHByZT5cclxufDEgMiAzIDQgNSA2IDcgOHxcclxufDMgMiA1IDQgMSA3IDggNnw8XC9wcmU+XHJcblxyXG48cD53ZSBoYXZlOjxcL3A+XHJcblxyXG48cHJlPlxyXG5QKDEpID0gM1xyXG5QKFAoMSkpID0gUCgzKSA9IDU8XC9wcmU+XHJcblxyXG48cD5hbmQ8XC9wPlxyXG5cclxuPHByZT5cclxuUChQKFAoMSkpKSA9IFAoNSkgPSAxPFwvcHJlPlxyXG5cclxuPHA+c28gdGhlIG1heGltdW0gaW4gdGhlIGN5Y2xlIG9mIDEgaXMgNS48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHdoaWNoIHRha2VzIGFzIGlucHV0IGludGVnZXJzIG4sIChuICZndDsgMCkgYW5kIGsgKCAxICZsZTsgayAmbGU7IG4pLCBhbmQgcmV0dXJucyB0aGUgbnVtYmVyIG9mIHBlcm11dGF0aW9ucyBvZiB0aGUgaW50ZWdlcnMgMSwuLi4sIG4sIGZvciB3aGljaCB0aGUgbWF4aW11bSBpbiB0aGUgY3ljbGUgb2YgMSBpcyBrLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXRjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICggMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgaXMgYSBzaW5nbGUgbGluZSB0aGF0IGNvbnRhaW5zIHRoZSB0aHJlZSBzcGFjZSBzZXBhcmF0ZWQgZGVjaW1hbCBpbnRlZ2VyIHZhbHVlcy4gVGhlIGZpcnN0IHZhbHVlIGlzIHRoZSBkYXRhIHNldCBudW1iZXIsIE4uIFRoZSBzZWNvbmQgdmFsdWUgaXMgdGhlIHNpemUgb2YgdGhlIHBlcm11dGF0aW9uLCBuIHdoZXJlICgxICZsZTsgbiAmbGU7IDIwKSwgYW5kIHRoZSB0aGlyZCB2YWx1ZSBpcyB0aGUgZGVzaXJlZCBtYXhpbXVtIGluIHRoZSBjeWNsZSBvZiAxLCBrIHdoZXJlICgxICZsZTsgayAmbGU7IG4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciAoTikgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IGEgZG91YmxlIHByZWNpc2lvbiBmbG9hdGluZyBwb2ludCB3aG9sZSB2YWx1ZSB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIHBlcm11dGF0aW9ucyBvZiB0aGUgaW50ZWdlcnMgMSwuLi4sIG4sIGZvciB3aGljaCB0aGUgbWF4aW11bSBpbiB0aGUgY3ljbGUgb2YgMSBpcyBrLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d