Logical Chain

Problem Description

Every time you come across a problem you've never seen before, haven't you thought of something that is familiar to you? If so, you might think of something else, then more and more things will come to your mind. This is what is called ''Logical Chain''. Lu Xun's work also described such interesting phenomenon.

Assume there are $n$ things, labeled by $1,2,...,n$. Little Q's mind can be expressed by a $n\times n$ matrix $g$. If he can think of $j$ when he comes across $i$, then $g_{i,j}$ is $1$, otherwise it's $0$. For two different things $u$ and $v$, if $u$ can lead to $v$ directly or indirectly and $v$ can also lead to $u$ directly or indirectly, then the pair $(u,v)$ is called a ''Looping Pair''. Little Q's mind changes all the time. On $i$-th day, there are $k_i$ positions $(u,v)$ in matrix $g$ flipped($0$ to $1$ and $1$ to $0$). Please write a program to figure out the number of ''Looping Pairs'' after each day's all changes. Note : $(u,v)$ and $(v,u)$ should not be counted twice.

Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases. In each test case, there are $2$ integers $n,m(1\leq n\leq 250,1\leq m\leq 25000)$ in the first line, denoting the number of things and days.\par For the next $n$ lines, each line contains $n$ integers $g_{i,1},g_{i,2},...,g_{i,n}(0\leq g_{i,j}\leq 1,g_{i,i}=0)$, denoting the matrix $g$. For the next $m$ parts, there is an integer $k_i(1\leq k_i\leq 10)$ in the first line, denoting the number of changes happened on that day. For the next $k_i$ lines, each line contains $2$ integers $u,v(1\leq u,v\leq n,u\neq v)$, denoting a changed position in $g$. It is guaranteed that each position will be changed at most once per day.

Output

For each day, print a single line containing an integer, denoting the number of ''Looping Pairs'' after that day's all changes.

Sample Input

1

4 2

0010

1000

0000

0000

3

1 4

3 2

1 2

2

4 3

2 3

Sample Output

3

6

Source

2017 Multi-University Training Contest - Team 4

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