Chef has N subordinates. In order to complete a very important order he will choose exactly K of them. He can't choose less than K since it will be not enough to complete the order in time. On the other hand if he chooses more than K subordinates he can't control them during the operation. Help him to find the number of ways he can choose the team to complete this very important order.

-----Input-----
The first line contains a single positive integer T <= 100, the number of test cases. T test cases follow. The only line of each test case contains two integers N and K, where 0 <= N, K < 2^64. It is guaranteed that the answer will be less than 2^64.

-----Output-----
For each test case, output a single line containing the number of ways to choose the required team.

-----Example-----
Input:
3
2 1
3 3
10 5

Output:
2
1
252

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def nCr(n, k):
	if k > n:
		return 0
	k = min(k, n - k)
	(num, den) = (1, 1)
	for i in range(k):
		num *= n - i
		den *= i + 1
	return num / den

def Main():
	for cases in range(int(input())):
		(a, b) = [int(x) for x in input().split()]
		print(nCr(a, b))
Main()


def gets():
	while 1:
		a = input().strip()
		if a:
			return a

def solve(n, k):
	if k > n:
		return 0
	k = min(k, n - k)
	(num, den) = (1, 1)
	for i in range(k):
		num *= n - i
		den *= i + 1
	return num / den

def Main():
	for cases in range(int(gets())):
		(a, b) = [int(x) for x in gets().split()]
		print(solve(a, b))
Main()


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
T = input()
T = int(T)
t = 1
while t <= T:
	s = input()
	s = s.split()
	t = t + 1
	N = int(s[0])
	K = int(s[1])
	if N < K:
		print('0')
		continue
	Kdash = N - K
	if Kdash < K:
		K = Kdash
	num = []
	denom = []
	for i in range(1, K + 1):
		denom.append(i)
	for i in range(N, N - K, -1):
		num.append(i)
	for i in range(0, K):
		for j in range(0, K):
			if denom[i] > 1:
				g = gcd(num[j], denom[i])
				denom[i] = denom[i] / g
				num[j] = num[j] / g
			else:
				break
	ret = 1
	for i in range(0, K):
		ret = ret * num[i]
	print(ret)


tests = int(input())
for test in range(tests):
	(n, k) = list(map(int, input().strip().split(' ')))
	if k > n:
		print(0)
	else:
		r = 1
		a = k
		b = n - k
		todo = []
		for i in range(1, min(a, b) + 1):
			todo += [i]
		j = 0
		i = max(a, b) + 1
		while i <= n:
			r *= i
			while j < len(todo) and r % todo[j] == 0:
				r /= todo[j]
				j = j + 1
			i = i + 1
		for i in range(j, len(todo)):
			r /= todo[i]
		print(r)


T = int(input())
while T:
	s = input().split(' ')
	N = int(s[0])
	K = int(s[1])
	if N < K:
		print('0')
	else:
		p = max(K, N - K)
		q = min(K, N - K)
		res = 1
		while N > p:
			res *= N
			N -= 1
		while q > 1:
			res /= q
			q -= 1
		print(res)
	T -= 1


t = int(input())
for i in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	if n == 0:
		if k == 0:
			print(1)
		else:
			print(0)
	elif k > n:
		print(0)
	else:
		if n - k < k:
			k = n - k
		ans = 1
		for i in range(n - k + 1, n + 1):
			ans *= i
		for i in range(1, k + 1):
			ans /= i
		print(ans)


T = int(input().strip('\n'))
for t in range(T):
	(n, k) = list(map(int, input().strip('\n').split()))
	if k > n:
		print(0)
		continue
	k = min(k, n - k)
	ans = 1
	for i in range(k):
		ans *= n - i
		ans /= i + 1
	print(ans)


from sys import stdin

def Choose(n, k):
	if n < 0 or k < 0 or k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(1, k + 1):
		res = res * (n - i + 1) / i
	return res
TC = int(stdin.readline().strip())
for tc in range(TC):
	(N, K) = list(map(int, stdin.readline().split()))
	print(Choose(N, K))


import decimal
import sys

def C(N, K):
	if K > N:
		return 0
	if N - K < K:
		K = N - K
	res = 1
	i = 1
	while i <= K:
		res = res * (N - K + i)
		res = int(res / i)
		i = i + 1
	return res
T = int(sys.stdin.readline())
for t in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	print(C(N, K))