f(n) is defined as: f(n) = 1^k+2^k+3^k+ ... +n^k, so it is the sum of the k-th power of all natural numbers up to n.

In this problem you are about to compute,

f(1) + f(2) + f(3) + ... + f(n)

Input

The first line is an integer T (1 ≤ T ≤ 54,321), denoting the number of test cases. Then, T test cases follow.

For each test case, there are two integers n (1 ≤ n ≤ 123,456,789) and k (0 ≤ k ≤ 321) written in one line, separated by space.

Output

For each test case output the result of the summatory function described above.

Since this number could be very large, output the answer modulo 1,234,567,891.

Example

Input:
5
2 3
10 3
3 3
100 0
100 1

Output:
10
7942
46
5050
171700

Warning: A naive algorithm may not run in time

See also: Another problem added by Tjandra Satria Gunawan