2277 - 【NOIP2016】D2T1 组合数问题

通过次数

6

提交次数

11

Time Limit : 1 秒
Memory Limit : 512 MB

Input

第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据,k 的意义见问题描述。
接下来 t 行每行两个整数 n, m,其中 n,m 的意义见问题描述。

Output

Examples

Input

1 2
3 3

Output

1

Input

2 5
4 5
6 7

Output

0
7

Hint

【数据说明】