题目背景

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

提示

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

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

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

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