J. Coconut vs Orange
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Currently, Coconut and Orange are running to be president of the United Fruits of Fruitmerica! Fruitmerica is made up of a $$$3$$$ by $$$N$$$ cities $$$(1 \le N \le 100)$$$, where each city contains either a $$$0$$$ or $$$1$$$, where $$$0$$$ represents voting for Coconut and $$$1$$$ represents voting for Orange. Additionally, Fruitmerica is divided up into $$$N$$$ districts, where each $$$N$$$ districts contains $$$3$$$ cities that form a connected component. In these districts, if $$$2$$$ or more cities votes for a candidate, that candidate wins that district. Currently, the districts are drawn as straight lines down. However, Coconut wants to redraw the districts in order to gain more votes. Coconut can redraw the districts however she wants, as long as there are $$$N$$$ districts with $$$3$$$ cities in each, and all the districts are connected components. What is the maximum number of districts Coconut can win?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains 1 integer $$$N$$$ ($$$1 \le N \le 100$$$).

The following $$$3$$$ lines contain $$$N$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is either $$$0$$$ or $$$1$$$.

Output

For each test case, output a single number, the most amount of districts Coconut can win.

Example
Input
3
3
0 1 0
1 0 1
1 1 0
4
1 0 0 1
0 1 1 0
0 1 0 1
2
0 1
1 0
1 1
Output
2
3
1