足球流氓主义是足球俱乐部支持者团伙之间为了恐吓和攻击其他球队支持者而产生的冲突。

不幸的是，在今年拜特兰德（Byteland）德比战之后，零号队和一号队的敌对球迷发生了冲突，并引发了骚乱。他们点燃了回收箱，砸碎了窗户，而警察试图通过发射催泪瓦斯来驱散人群。许多人被捕，为了防止监狱中发生更多的斗殴，当局要求你根据以下规则重新设计监狱：

• 监狱是一个 $N \times 2$ 的网格，每个囚犯被分配到一个单独的单元格中。
• 你可以合并相邻的单元格以构建更大的单元格，但只能构建矩形单元格。
• 单元格不能重叠，囚犯不能移动。
• 每名囚犯要么支持零号队，要么支持一号队。
• 同一个单元格内的所有囚犯必须支持同一支球队。
• 拜特兰德人非常善于社交，你必须尽量减少单独监禁（即只有一个囚犯的单元格），因为囚犯在单独监禁时可能会感到孤独并自杀。

你需要回答的问题是：假设你以最优方式合并单元格，单独监禁的最小数量是多少？

输入格式

你的程序将在一个或多个测试用例上进行测试。第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。每个测试用例以包含整数 $N$ ($1 \le N \le 10^4$) 的行开始，表示网格的长度。接下来的 $N$ 行，每行包含一个长度为 2 的字符串，表示第 $i$ 行两个单元格中囚犯支持的球队。球队编号可以取 0 或 1。

输出格式

对于每个测试用例，打印一行，包含单独监禁的最小数量。

样例

输入 1

2
6
01
01
01
01
10
00
4
00
10
10
10

输出 1

2
0