Rohit dreams he is in a shop with an infinite amount of marbles. He is allowed to select n marbles. \
There are marbles of k different colors. From each color there are also infinitely many marbles. \
Rohit wants to have at least one marble of each color, but still there are a lot of possibilities for his selection. In his effort to make a decision he wakes up. \
Now he asks you how many possibilities for his selection he would have had. \
Assume that marbles of equal color can't be distinguished, and the order of the marbles is irrelevant.

------ Input Format ------ 

The first line of input contains a number T ≤ 100 that indicates the number of test cases to follow. \
Each test case consists of one line containing n and k, where n is the number of marbles Rohit selects and k is the number of different colors of the marbles. 

------ Output Format ------ 

For each test case print the number of possibilities that Rohit would have had.
You can assume that this number fits into a signed 64 bit integer.

------ Constraints ------ 

- 1≤k≤n≤1000000

----- Sample Input 1 ------ 
2
10 10
30 7

----- Sample Output 1 ------ 
1
475020

Source: codechef | Difficulty: EASY
Tags: Combinatorics

Square root algorithms

Mathematics


Solutions:
import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(math.comb(n - 1, k - 1))


import math
a = int(input())
for i in range(a):
	(n, k) = map(int, input().split(' '))
	print(math.comb(n - 1, k - 1))


import math
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	num_possibilities = math.comb(n - 1, k - 1)
	print(num_possibilities)


import math
for i in range(int(input())):
	(select, different_colours) = map(int, input().split())
	print(math.comb(select - 1, different_colours - 1))


import math
for i in range(int(input())):
	data = input().split()
	selected = int(data[0])
	diff_colours = int(data[1])
	print(math.comb(selected - 1, diff_colours - 1))


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(math.comb(x - 1, y - 1))


import math as m
import random as u
for _ in range(int(input())):
	(n, tyui) = map(int, input().split())
	print(m.comb(n - 1, tyui - 1))


def c(n, r):
	res = 1
	if r > n // 2:
		r = n - r
	for i in range(r):
		res *= n
		res //= i + 1
		n -= 1
	return res
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	print(c(n - 1, n - k))


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	print(math.comb(a - 1, b - 1))


import math as m
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(m.comb(a - 1, b - 1))


import math
goals = int(input())
for distractions in range(goals):
	(life, wife) = map(int, input().split(' '))
	print(math.comb(life - 1, wife - 1))


from math import comb
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	print(comb(n - 1, k - 1))


import math
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	c = math.comb(x - 1, y - 1)
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	num = 1
	for i in range(1, k):
		num *= n - k + i
		num //= i
	print(num)


import math
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(math.comb(a - 1, b - 1))


import math as m
for t in range(int(input())):
	(marbles, color) = map(int, input().split())
	print(m.comb(marbles - 1, color - 1))


T = int(input())
for i in range(0, T):
	(n, k) = map(int, input().split())
	ans = 1
	for j in range(1, k):
		ans *= n - k + j
		ans //= j
	print(int(ans))


import math
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	print(math.comb(n - 1, k - 1))
	t -= 1


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	print(math.comb(n - 1, m - 1))