题目描述

给定 T 组查询，每组查询包含两个非负整数 n 和 k，请你计算组合数 C (n, k) 的结果。其中组合数 C (n, k) 表示从 n 个不同元素中选出 k 个元素的方案数，定义如下：

• 当 k > n 时，C (n, k) = 0
  

• 当 0 ≤ k ≤ n 时，计算组合数 C (n, k)  的结果。
  

输入描述:

第一行包含一个整数 T（1 ≤ T ≤ 2e6），表示查询组数。接下来 T 行，每行包含两个整数 n 和 k（1 ≤ n ≤ 18，0 ≤ k ≤ 18）。

输出描述:

对于每组查询，输出一个整数，表示 C (n, k) 的结果。

示例1

4
5 2
6 3
3 5
10 0

10
20
0
1

Limitation

2s, 1024KiB for each test case.