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 

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