Migrated from Lutece 1848 柱爷搞搞搞搞搞毒毒毒毒毒瘤瘤瘤瘤瘤（Legendary Version）

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有一条长度为$N$的线段,初始每个位置颜色都是$0$.

有$K$次操作,第$i$次操作可以任选一段线段上的非空区间并将这个选择的区间颜色改为$i$.

求$K$次操作后,一共有多少种可能的线段?

输出取模$163577857$后的答案.

Input

输入只有一行有一个整数$T$,表示数据组数.

接下来$T$行，每行两个整数$N$和$K$.

数据保证:

• $1 \leq T \leq 100$
• $1 \leq N \leq 10^6$
• $1 \leq K \leq N$
• $1 \leq \sum N \leq 5 \cdot 10^6$

Output

对每组数据，输出答案.

Samples

11
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
772002 772002

1
3
5
6
17
34
10
45
130
289
59572204

Note

现已经加入豪华毒瘤套餐.

Resources

每周一题 Div772002