Sum of Army Ability Values

Steve has a total of $t$ armies; each army is arranged in an $n\times k$ formation with each army having a distinct number of soldiers. The position of each soldier is denoted by $(x,y)$ with $0 \le x < n$ and $0 \le y < k$, and the soldier's index is defined as $i=x\cdot k+y$. The captain, located at $(0,0)$, is always dispatched. For every other soldier, there is a choice: dispatch or not. The ability value of an $n\times k$ army is defined as follows:

• If all soldiers are dispatched, the ability value is $1$.
• Otherwise, for each soldier at position $(x,y)$ (with index $i=x\cdot k+y$) that is not dispatched, the current ability value is multiplied by ( \frac{x}{i-x} ; = ; \frac{x}{x\cdot(k-1)+y}) (note that for soldiers in the first row with $x=0$, this fraction equals $0$ for $y>0$).

For example, consider a $2\times2$ army:

• If only the soldier at $(1,1)$ (index $3$) is not dispatched, the ability value becomes (\frac{1}{3-1}=\frac{1}{2}).
• If the soldiers at $(1,1)$ (index $3$) and $(0,1)$ (index $1$) are not dispatched, the ability value becomes (\frac{1}{3-1}\times\frac{0}{1-0}=0).
• If the soldiers at $(1,1)$ (index $3$) and $(1,0)$ (index $2$) are not dispatched, the ability value becomes (\frac{1}{3-1}\times\frac{1}{2-1}=\frac{1}{2}).

Observe that the sum over all possible dispatch schemes equals the product of independent choices for each soldier (except the captain who is always dispatched). For each soldier, the contribution is [ 1+ \frac{x}{x\cdot(k-1)+y} ;=; \frac{x\cdot(k-1)+y+x}{x\cdot(k-1)+y} = \frac{x\cdot k+y}{x\cdot(k-1)+y}. ]

Since the soldiers in the first row (except the captain) yield a factor of $1$, the total sum over all schemes is given by [ S=\prod_{x=1}^{n-1}\prod_{y=0}^{k-1} \frac{x\cdot k+y}{x\cdot(k-1)+y}. ]

The answer for each army is obtained as follows. Express (S) as a reduced fraction (\frac{p}{q}). You are required to find the smallest nonnegative integer (a) such that [ p\equiv q\cdot a \pmod{1145141}, ] and output (a). If no such integer exists (which happens when (q) is divisible by the prime modulus (1145141)), output (-1).

Note: In the special case where (k=1), observe that for any soldier with (x\ge 1) the factor (\frac{x}{x\cdot(0)+0}) is undefined; hence the only valid scheme is to dispatch all soldiers, so (S=1).

inputFormat

The first line contains an integer $t$, the number of armies (test cases). Each of the following $t$ lines contains two integers $n$ and $k$, representing the number of rows and columns of the army formation, respectively.

outputFormat

For each test case, output on a separate line the smallest nonnegative integer $a$ satisfying $p\equiv q\cdot a \pmod{1145141}$, where $\frac{p}{q}$ is the reduced fraction of the sum of ability values. If no such integer exists, output $-1$.

sample

3
2 2
1 3
3 1

3
1
1