1129. 考新郎

單點時限: 2.0 sec

記憶體限制: 256 MB

國慶期間，省城 HZ 剛剛舉行了一場盛大的集體婚禮，為了使婚禮進行的豐富一些，司儀臨時想出了有一個有意思的節目，叫做「考新郎」， 具體的操作是這樣的：

首先，給每位新娘打扮得幾乎一模一樣，并蓋上大大的紅蓋頭随機坐成一排；

然後，讓各位新郎尋找自己的新娘。每人隻準找一個，并且不允許多人找一個。

最後，揭開蓋頭，如果找錯了對象就要當衆跪搓衣闆……

看來做新郎也不是容易的事情……

假設一共有 N 對新婚夫婦，其中有 M 個新郎找錯了新娘，求發生這種情況一共有多少種可能。

輸入格式

輸入資料的第一行是一個整數 C, 表示測試執行個體的個數，然後是 C 行資料，每行包含兩個整數 N 和 M (1<M≤N≤20)。

輸出格式

對于每個測試執行個體，請輸出一共有多少種發生這種情況的可能，每個執行個體的輸出占一行。

樣例

input

2

2 2

3 2

output

1

3

全錯排參見

/*
思路：先從n中選擇出m的個數就是組合C（n,m）個，m個全排錯的個數公式f[m]=(m-1)*(f[m-2]+f[m-1])
*/
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll fun(int n,int m) {
	ll ans=1;
	for(int i = 1; i <= m; i++)
		ans=ans*(n-i+1)/i;
	return ans;
}
int main() {
	int t;
	cin>>t;
	long long f[21];
	f[0]=0;
	f[1]=0;
	f[2]=1;
	for(int i = 3; i < 21; i++)
		f[i]=(f[i-1]+f[i-2])*(i-1); 
	for(int i = 0; i < t; i++) {
		int n,m;
		cin>>n>>m;
		ll ans=0;
		ans=f[m]*fun(n,m);
		cout<<ans<<endl;
	}
	return 0;
}