Summation of Partial Binomial Coefficients

Sho Miko discovered an interesting thing called binomial coefficient. Given the classical definition:

For two non‐negative integers \(m\) and \(n\) with \(m \le n\), the binomial coefficient is defined as \[ C_n^m = \frac{n!}{m!(n-m)!}, \] which represents the number of ways to choose \(m\) elements from \(n\) elements.

For example, in a game scenario with 4 characters where every day 2 characters are paired up, there are \(C_4^2 = 6\) possible pairings.

Now, given two positive integers \(n\) and \(m\), Sho Miko wishes to compute the value of the following double summation:

[ S(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m} \tilde{C}_j^i, ]

where the term \(\tilde{C}_j^i\) is defined as follows:

• If \(i \le j\), then \(\tilde{C}_j^i = C_j^i = \frac{j!}{i!(j-i)!}\).
• If \(i > j\), then \(\tilde{C}_j^i = 0\) (by definition).

Your task is to compute \(S(n,m)\) modulo \(19260817\) for multiple queries. Note that you do not need to take any additional mod besides \(19260817\).

inputFormat

The first line contains an integer \(q\) \( (1 \le q)\) denoting the number of queries. Each of the following \(q\) lines contains two positive integers \(n\) and \(m\) separated by a space.

It is guaranteed that the given values are such that the answer can be computed within the time limits.

outputFormat

For each query, output a single line containing the value of \(S(n, m)\) modulo \(19260817\).

sample

3
2 3
4 4
1 5

10
26
15