A. 姬哥的约会计划

众所周知姬哥是一个海王，目前姬哥有两个女朋友，她们分别是金陵特产一号和金陵特产二号。

姬哥知道接下来 $n$ 天内，两位女朋友每天的安排，简略起见，我们用 $a_i(a_i \in {0,1})$ 描述金陵特产一号第 $i$ 天是否有空， $a_i = 1$表示金陵特产一号第 $i$ 天有空，可以和姬哥约会，$a_i = 0$表示金陵特产一号没有空，不能和姬哥约会。

同理 $b_i = 1$表示金陵特产二号第 $i$ 天可以和姬哥约会，$b_i = 0$表示金陵特产二号不能和姬哥约会。

姬哥每天可以选择一个女朋友约会，或者呆在家里，他希望接下来 $n$ 天中外出约会的天数尽量多，然而如果姬哥在相邻的两天中与不同的女朋友约会就有暴露的风险，他希望避免这种情况。

现在希望你计算出姬哥在接下来 $n$ 天中最多能约会多少天且任意相邻的两天中不能与不同的女友约会。

输入数据的第一行一个整数 $T(1\leq T\leq 10)$，表示测试数据组数。

接下来每个测试数据第一行一个整数 $n (1\leq n\leq 10^3)$。

接下来 $n$ 行，每行有两个整数，第 $i$ 行的两个数字分别为 $a_i,b_i(a_i,b_i \in {0,1})$。

对于每组测试数据请输出一行一个整数表示姬哥所能约会的最大天数。

样例输入

2
5
1 1
1 1
1 1
1 1
1 1
4
1 0
0 1
1 0
0 1

样例输出

5
2