축구 훌리건

축구 훌리건은 다른 팀 서포터를 위협하고 물리적으로 공격할 목적으로 결성된 축구 클럽 서포터 갱단 사이의 충돌이다.

올해 팀 0과 팀 1의 바이텔란 클라시코가 끝난 뒤, 라이벌 팬들이 서로 충돌하고 진압 경찰과 맞섰다. 그들은 재활용 쓰레기통에 불을 지르고 유리창을 부쉈으며, 경찰은 최루탄을 쏘아 해산시키려 했다. 많은 사람이 체포되었지만, 교도소에서 더 많은 싸움이 일어나는 것을 막기 위해 당국은 다음 규칙에 따라 교도소를 다시 설계해 달라고 요청했다.

• 교도소는 N행 2열의 동일한 격자이며, 각 수감자는 한 칸에 배정된다.
• 인접한 칸을 합쳐 더 큰 칸을 만들 수 있지만, 직사각형이어야 한다.
• 칸은 겹칠 수 없고 수감자를 옮길 수 없다.
• 각 수감자는 팀 0 또는 팀 1을 지지한다.
• 같은 칸에 있는 모든 수감자는 같은 팀을 지지해야 한다.
• 바이텔란 사람들은 매우 사교적이므로, 수감자가 외로움을 느껴 자살할 수 있는 독방(수감자가 한 명뿐인 칸)의 수를 최소화해야 한다.

당신은 다음 질문에 답해야 한다. 칸을 최적으로 합칠 때 독방의 최소 수는 얼마인가?

프로그램은 하나 이상의 테스트 케이스로 채점된다. 첫 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 격자의 길이를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 있는 줄로 시작한다.

이어서 N개의 줄이 주어지며, 각 줄에는 i번째 행의 1번과 2번 칸에 있는 수감자가 각각 지지하는 팀을 나타내는 길이 2의 문자열이 있다. 팀은 ‘0’ 또는 ‘1’의 값을 가진다.

각 테스트 케이스마다 독방의 최소 수를 한 줄에 출력한다.