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.

----- Sample Input 1 ------ 
3
2 1
3 3
10 5
----- Sample Output 1 ------ 
2
1
252

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
def choose(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
T = 1
T = int(input().strip())
for _ in range(T):
	(n, k) = map(int, input().split())
	print(int(choose(n, k)))


from sys import stdin
from math import *

def sin():
	return stdin.readline()

def cm(n, k):
	if n < k:
		return 0
	if k > n - k:
		k = n - k
	p = 1
	for i in range(1, k + 1):
		d = gcd(p, i)
		p //= d
		p *= (n - i + 1) // (i // d)
	return p
for _ in range(int(sin())):
	(n, r) = map(int, sin().split())
	print(cm(n, r))


import os
import sys
import collections
__DEBUG__ = 0

def read_int():
	return int(input())

def read_ints():
	return list(map(int, input().split()))

def read_split_ints():
	return list(map(int, list(input())))

def read_float():
	return float(input())

def debug(*args):
	if __DEBUG__:
		print('[DEBUG]: ', *args)

def dump_1d(name, array):
	if not __DEBUG__:
		return
	for i in range(len(array)):
		print('{}[{}]: {}'.format(name, i, array[i]))
	print()

def dump_2d(name, array):
	if not __DEBUG__:
		return
	for i in range(len(array)):
		for j in range(len(array[i])):
			print('{}[{}][{}]: {}'.format(name, i, j, array[i][j]))
	print()

def product(array):
	ans = 1
	for i in array:
		ans *= i
	return ans

def nCm(n, m):
	m = min(m, n - m)
	return product(range(n - m + 1, n + 1)) // product(range(1, m + 1))

def proc_case():
	(N, K) = read_ints()
	if N < K:
		return 0
	return nCm(N, K)

def main():
	T = read_int()
	debug('T ', T)
	for i in range(T):
		ans = proc_case()
		print(ans)
main()


def binom(n, r):
	if 2 * r > n:
		r = n - r
	if r < 0:
		return 0
	bnm = 1
	for t in range(1, r + 1):
		bnm *= n + 1 - t
		bnm //= t
	return bnm
t = int(input())
for ti in range(t):
	(n, k) = map(int, input().split())
	print(binom(n, k))


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a < b:
		print(0)
		continue
	print(ncr(a, b))


def choose(n, r):
	if r < 0 or r > n:
		return 0
	if r > n - r:
		r = n - r
	prod = 1
	for i in range(r):
		prod *= n - i
		prod //= i + 1
	return prod
t = int(input())
for it in range(t):
	(n, k) = [int(word) for word in input().split()]
	print(choose(n, k))


def C(n, k):
	if k <= n:
		tmpn = 1
		tmpk = 1
		for t in range(1, min(k, n - k) + 1):
			tmpn *= n
			tmpk *= t
			n -= 1
		return tmpn // tmpk
	else:
		return 0
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	result = C(n, k)
	print(result)


def com(a, b):
	if b >= 0 and a >= 0:
		if b > a:
			return 0
		if a == b:
			return 1
		if b == 0:
			return 1
		r = max(b, a - b)
		up = down = 1
		for i in range(r + 1, a + 1):
			up *= i
		for i in range(1, a - r + 1):
			down *= i
		return up // down
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(com(a, b))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
	else:
		val = 1
		k = min(k, n - k)
		for i in range(k):
			val = val * (n - i)
			val = val // (i + 1)
		print(int(val))


from functools import reduce

def ncr(n, r):
	if r > n:
		return 0
	if n == r or r == 0:
		return 1
	r = max(r, n - r)
	above = reduce(lambda x, y: x * y, range(n, r, -1))
	bottom = reduce(lambda x, y: x * y, range(n - r, 0, -1))
	return above // bottom
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(ncr(n, k))


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def choose(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def alg(N, K):
	return choose(N, K)

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		(N, K) = list(map(int, data.readline().split()))
		res = alg(N, K)
		print(res)
main()


def getAns(N, K):
	ans = 1
	for r in range(1, K + 1):
		ans = ans * (N - r + 1) // r
	return ans
for tc in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	if K > N or K < 0:
		print(0)
	else:
		print(getAns(N, min(K, N - K)))


import sys
ttt = int(sys.stdin.readline().strip())
for i in range(ttt):
	(n, k) = map(int, sys.stdin.readline().strip().split())
	if k < 0 or k > n:
		res = 0
	else:
		if 2 * k > n:
			k = n - k
		res = 1
		for j in range(k):
			res *= n - j
		for j in range(1, k + 1):
			res //= j
	print(res)


import functools

def ncr(n, r):
	r = min(r, n - r)
	a = functools.reduce(lambda x, y: x * y, range(n, n - r, -1), 1)
	b = functools.reduce(lambda x, y: x * y, range(1, r + 1), 1)
	return a // b
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
	else:
		print(ncr(n, k))


def get_ans(n, k):
	ans = 1
	if n < k:
		return 0
	k = min(k, n - k)
	for i in range(1, k + 1):
		ans *= n - i + 1
		ans //= i
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(get_ans(n, k))


import operator as op
from functools import reduce
from math import *
t = int(input())
for _ in range(t):
	(n, r) = map(int, input().split())
	if n < r:
		print(0)
		continue
	r = min(r, n - r)
	nu = reduce(op.mul, range(n, n - r, -1), 1)
	de = reduce(op.mul, range(1, r + 1), 1)
	print(nu // de)


import math

def c_fact(a, b):
	res = 1
	for x in range(b + 1, a + 1):
		res *= x
	return res
for t in range(int(input())):
	(n, r) = map(int, input().split())
	if n >= r:
		x = c_fact(n, max(r, n - r)) // math.factorial(min(r, n - r))
		print(x)
	else:
		print(0)


def fact(n):
	if n == 0 or n == 1:
		return 1
	else:
		return n * fact(n - 1)
n = int(input())
while n > 0:
	s = input()
	(a, b) = [int(i) for i in s.split(' ')]
	if b > a:
		print('0')
	else:
		c = a - b
		if b > c:
			x = b
			b = c
			c = x
		num = 1
		den = fact(b)
		for i in range(a, c, -1):
			num = num * i
		print(num // den)
	n = n - 1


fact = [None] * 40000
fact[0] = 1
for i in range(1, 40000):
	fact[i] = fact[i - 1] * i
t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	if n < k:
		print(0)
		continue
	k = min(k, n - k)
	if k == 0:
		print(1)
	elif k == 1:
		print(n)
	elif k == 2:
		print(n * (n - 1) // 2)
	elif k == 3:
		print(n * (n - 1) * (n - 2) // 6)
	elif k == 4:
		print(n * (n - 1) * (n - 2) * (n - 3) // 24)
	else:
		print(fact[n] // (fact[k] * fact[n - k]))


import math
for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	k = temp[1]
	if n < k:
		print(0)
		continue
	elif k == 0 or k == n:
		print(1)
		continue
	elif n == 0:
		print(1)
		continue
	if k > n - k:
		k = n - k
	ans = n
	i = 2
	while i <= k:
		ans *= n - i + 1
		ans //= i
		i += 1
	print(ans)


from math import factorial as f

def ncr(n, r):
	if r > n:
		return 0
	a = n
	b = r
	c = n - r
	d = max(b, c)
	e = min(b, c)
	e = f(e)
	ans = 1
	for i in range(d + 1, n + 1):
		ans *= i
	return ans // e
t = int(input())
for _ in range(t):
	(n, r) = map(int, input().split())
	print(ncr(n, r))


t = int(input())
while t > 0:
	m = 1
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
	else:
		if n - k < k:
			k = n - k
		i = n
		while i > n - k:
			m = m * i
			i -= 1
		o = 1
		while k > 0:
			o = o * k
			k -= 1
		print(m // o)
	t -= 1


def main():
	from sys import stdin, stdout
	for _ in range(int(stdin.readline())):
		(n, r) = map(int, stdin.readline().split())
		if n >= r:
			r = min(n - r, r)
			if r:
				for i in range(n - 1, n - r, -1):
					n *= i
				for i in range(r, 1, -1):
					n //= i
			else:
				n = 1
		else:
			n = 0
		stdout.write(str(n) + '\n')
main()


t = int(input())
for testcase in range(0, t):
	s = input()
	s = list(s.split())
	n = int(s[0])
	k = int(s[1])
	a = []
	num = 1
	den = 1
	a.append(1)
	if k > n:
		x = 0
	else:
		if k >= n - k:
			i = k + 1
			while i <= n:
				num = num * i
				i = i + 1
		else:
			i = n - k + 1
			while i <= n:
				num = num * i
				i = i + 1
		if k >= n - k:
			i = 1
			while i <= n - k:
				den = den * i
				i = i + 1
		else:
			i = 1
			while i <= k:
				den = den * i
				i = i + 1
		x = num // den
	print(x)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
while t > 0:
	m = 1
	(n, k) = map(int, input().split())
	if k > n:
		print(0)
	else:
		if n - k < k:
			k = n - k
		i = 1
		ans = 1
		while i < k + 1:
			l = gcd(ans, i)
			ans = ans // l
			c = i // l
			ans *= (n - i + 1) // c
			i += 1
		print(ans)
	t -= 1


def alg(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
t = int(input())
for i in range(t):
	(n, r) = map(int, input().split())
	result = alg(n, r)
	print(result)


t = int(input())
for i in range(t):
	L = list(map(int, input().split()))
	n = L[0]
	k = L[1]
	if k == 0 or k == n:
		print(1)
	elif k > n:
		print(0)
	elif max(k, n - k) == k:
		ans = 1
		for j in range(k + 1, n + 1):
			ans *= j
		for j in range(2, n - k + 1):
			ans //= j
		print(ans)
	else:
		ans = 1
		for j in range(n - k + 1, n + 1):
			ans *= j
		for j in range(2, k + 1):
			ans //= j
		print(ans)


from math import factorial as fact
import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	if N < K:
		print(0)
	else:
		print(ncr(N, K))