You are given a function $f(n,k) = \sum_{s=0}^{s=n} \sum_{r=s}^{r=n} \sum_{t=0}^{t=s} \frac {\binom nr \binom rs \binom st t(3k^2)^{t/2} I(t)}{(s+1)}$

where $I(x) = \begin{cases} 1 & x \equiv 0\ (mod\ 4) \\ 0 & x \equiv 1\ (mod\ 4) \\ -1 & x \equiv 2\ (mod\ 4) \\ 0 & x \equiv 3\ (mod\ 4) \\ \end{cases}$

and $\binom nr$ known as Binomial Coefficient denotes the number of ways to choose an unordered subset of $r$ elements from a fixed set of $n$ elements.

You must find the value of $f(n,k)$ (modulo $10^9+21$).

Integers $n$ and $k$ are given to you.

Input format

• The first line consists of a single integer $T$ denoting the number of test cases.
• Each of the next $T$ lines consists of two space-separated integers $n$ and $k$ respectively.

Output format

The output should consist of $T$ lines each containing a single integer corresponding to the required value $f(n,k)$.

Print the answer modulo $10^9+21$. If the answer is of the form $\frac PQ$, then print $PQ^{-1} (mod\ 10^9+21)$.

Constraints

$1\le T \le 10^5\\ 1\le n \le 10^{18}\\ 0\le k \le 10^{18}$