题目背景

WD整日沉浸在循环中，无法自拔……

题目描述

这天，WD蒟蒻为了解决一个小问题写了个很长很长的for循环：

int cnt = 0;
for (int a_1 = 0; a_1 <= m; a_1++) {
    for (int a_2 = 0; a_1 + a_2 <= m; a_2++) {
    ...
        for (int a_n = 0; a_1 + a_2 + ... + a_n <= m; a_n++) {
            cnt = (cnt + 1) % 19491001;
        }
    }
}
printf("%d\n", cnt);

CX过来看了一眼，说：**WD你个笨蛋，这道题不是SB题吗？**WD一脸懵逼，只好请你来教教他啦……

输入格式

第一行一个数$T$，表示数据组数。接下来每行两个数$n,m$，分别表示循环重数和每层循环的上界。

输出格式

共$T$行，每行一个数表示答案。

2
2 9
10 14

55
1961256

提示

$subtask1(23pts):~n,m\le 1,000,~1\le T\le 10,000$

$subtask2(35pts):~n,m\le 10^7,~1\le T\le 5$

$subtask3(42pts):~n,m\le 10^{18},~1\le T\le 100,000$

对于样例1，写个代码就知道答案是55了（大雾）。