Holy Shit

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

calculate a matrix A which is obtained when adding matrix B^n recursively to unit matrix I, ie, I+B+B^2+B^3+...B^n.Notice that B is a formal matrix whose number of rows and columns are equal.

Input

The first line contains an integer t ( 1 <= t <= 10 ): the number of test cases. Then for each test case:The first line contains two integers n,k ( 1 <= n<= 10^8 ,2 <= k <= 20 ),where k is the size of matrix B.

Output

For each test case, output the result in the form of sample.You should print the case number and matrix A.Each element of matrix should be mod 10007

Sample Input

1
3 2
1 0
1 1

Sample Output

Case 1:
4 0
6 4

Hint

None

Source

陶翔专场练习赛

提交代码