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

Difficulty: interview

Starter code:

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)
 else:
  if 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)





#!/usr/bin/env python

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))



#!/usr/bin/python
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))