Big Integer

Problem Description

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.

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 :

Input

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$.

Output

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

Sample Input

1

3 2 2

101

010

1 1

1 2

Sample Output

13

Hint

cnt(0)=4 : 112,121,211,2. cnt(1)=6 : 112,121,211,2,12,21. cnt(2)=3 : 2,12,21.

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6067