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}\)