Killjee is very weak in mathematics and everyone is sure that he will fail in mathematics this year like previous years. Somehow killjee found the question of final exams and now he is asking for your help to solve the question.

$S_{k} = \prod_{i = 0}^{r - 1} \binom{k - \frac{i \cdot (i +1)}{2}}{i + 1}$

$SS = \sum_{k = \frac{r \cdot (r + 1)}{2}}^{n} \binom{n}{k} \cdot S_{k}$

Compute $SS$.

Input:

First line of input contains a single integer T denoting the number of test cases. Each of the next T lines contains 2 integers, n and r, as described in the problem statement.

Output:

Print the answer to each query modulo $10^{10}+19$.

Constraints:

$1 \le T \le 10$

$1 \le n \le 10^{18}$

$1 \le r \le 2000$