Little Q likes positive big integers in base $k$, but not all big integers. He doesn't like integers with zeroes, including leading zeroes. He is even particular with the occurrence of each digit. Formally it can be described as a matrix $g_{1..k-1,0..n}$, for every digit $i$ from $1$ to $k-1$, he doesn't like integers having exactly $j$-digit $i$ when $g_{i,j}=0$. He also can't accept any digit appearing more than $n$ times.

Picture from Wikimedia Commons


Little Q's taste changes every day. There are $m$ days in total, on $i$-th day $g_{u_i,v_i}$ flipped($0$ to $1$ and $1$ to $0$). Let $cnt(i)$ denotes the number of big integers Little Q likes after $i$-th day's change, where $cnt(0)$ denotes the answer before all changes. Your task is to calculate the following thing :
\begin{eqnarray*}
\left(\sum_{i=0}^m cnt(i)\right)\bmod 786433
\end{eqnarray*}

The first line of the input contains an integer $T(1\leq T\leq5)$, denoting the number of test cases.

In each test case, there are $3$ integers $k,n,m(3\leq k\leq 10,1\leq n\leq 14000,1\leq m\leq 200)$ in the first line, denoting the base, the upper limit and the number of days.

For the next $k-1$ lines, each line contains $n+1$ integers $g_{i,0},g_{i,1},...,g_{i,n}(0\leq g_{i,j}\leq 1)$, denoting the matrix $g$.

For the next $m$ lines, each line contains $2$ integers $u_i,v_i(1\leq u_i\leq k-1,0\leq v_i\leq n)$, denoting a changed position in $g$.

For each test case, print a single line containing an integer, denoting the answer.