시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB103574854.545%

문제

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+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAxLCAuLi4gblx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjFjXHVjNWY0IFx1YzkxMVx1YzVkMCBcdWNkNWNcdWIzMDAgXHVjMGFjXHVjNzc0XHVkMDc0IDFcdWM3NTggXHVhYzEyXHVjNzc0IGtcdWM3NzggXHVjMjFjXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjY4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1heGltdW0gaW4gdGhlIEN5Y2xlIG9mIDEiLCJkZXNjcmlwdGlvbiI6IjxwPklmIFAgaXMgYSBwZXJtdXRhdGlvbiBvZiB0aGUgaW50ZWdlcnMgMSwuLi4sIG4sIHRoZSBtYXhpbXVtIGluIHRoZSBjeWNsZSBvZiAxIGlzIHRoZSBtYXhpbXVtIG9mIHRoZSB2YWx1ZXMgUCgxKSwgUChQKDEpKSwgUChQKFAoMSkpKSwgZXRjLiBGb3IgZXhhbXBsZSwgaWYgUCBpcyB0aGUgcGVybXV0YXRpb246PFwvcD5cclxuXHJcbjxwcmU+XHJcbnwxIDIgMyA0IDUgNiA3IDh8XHJcbnwzIDIgNSA0IDEgNyA4IDZ8PFwvcHJlPlxyXG5cclxuPHA+d2UgaGF2ZTo8XC9wPlxyXG5cclxuPHByZT5cclxuUCgxKSA9IDNcclxuUChQKDEpKSA9IFAoMykgPSA1PFwvcHJlPlxyXG5cclxuPHA+YW5kPFwvcD5cclxuXHJcbjxwcmU+XHJcblAoUChQKDEpKSkgPSBQKDUpID0gMTxcL3ByZT5cclxuXHJcbjxwPnNvIHRoZSBtYXhpbXVtIGluIHRoZSBjeWNsZSBvZiAxIGlzIDUuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCB0YWtlcyBhcyBpbnB1dCBpbnRlZ2VycyBuLCAobiAmZ3Q7IDApIGFuZCBrICggMSAmbGU7IGsgJmxlOyBuKSwgYW5kIHJldHVybnMgdGhlIG51bWJlciBvZiBwZXJtdXRhdGlvbnMgb2YgdGhlIGludGVnZXJzIDEsLi4uLCBuLCBmb3Igd2hpY2ggdGhlIG1heGltdW0gaW4gdGhlIGN5Y2xlIG9mIDEgaXMgay48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0Y29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoIDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGlzIGEgc2luZ2xlIGxpbmUgdGhhdCBjb250YWlucyB0aGUgdGhyZWUgc3BhY2Ugc2VwYXJhdGVkIGRlY2ltYWwgaW50ZWdlciB2YWx1ZXMuIFRoZSBmaXJzdCB2YWx1ZSBpcyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBOLiBUaGUgc2Vjb25kIHZhbHVlIGlzIHRoZSBzaXplIG9mIHRoZSBwZXJtdXRhdGlvbiwgbiB3aGVyZSAoMSAmbGU7IG4gJmxlOyAyMCksIGFuZCB0aGUgdGhpcmQgdmFsdWUgaXMgdGhlIGRlc2lyZWQgbWF4aW11bSBpbiB0aGUgY3ljbGUgb2YgMSwgayB3aGVyZSAoMSAmbGU7IGsgJmxlOyBuKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIgKE4pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSBhIGRvdWJsZSBwcmVjaXNpb24gZmxvYXRpbmcgcG9pbnQgd2hvbGUgdmFsdWUgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBwZXJtdXRhdGlvbnMgb2YgdGhlIGludGVnZXJzIDEsLi4uLCBuLCBmb3Igd2hpY2ggdGhlIG1heGltdW0gaW4gdGhlIGN5Y2xlIG9mIDEgaXMgay48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d