Problem Description

There are strings of length $L$ consisting of the first $k$ $(2\le k\le 26)$ lowercase letters.The total number of strings is $k^L$.

For each pair$(i,j)$($\ 0\leq i,j\leq n-1\ $),please count the number of strings which contain $p$ lowercase letters 'a' and $q$ lowercase letters 'b', satisfying $p \equiv i\ (mod\ n) $ and $ q \equiv j\ (mod\ n) $ .

Print the matrix $A$,$A[i][j]$ is the answer of pair$(i,j)$.

Input

The first line contains an integer $T(T \le 10)$. Then $T$ test cases follow.
For each test case the first line contains three integers $k(2\le k\le 26)$,$L(1\le L\le 10
^{18})$,$n(1\le n\le 500)$.
$\sum n\le 2000$.

Output

For each test case, output $n$ lines contain $n$ integers.
which is the answer modulo $P=10^9+9$,satisfying $n|(P-1)$.

1
2 1 3

0 1 0
1 0 0
0 0 0