statement.md

白黒分け

Problem Statement

簡単なゲームをしよう。

白い碁石と黒い碁石が横1列に混ざって並べられている。 隣り合った碁石を入れ替えることを1手とし、左側に白い碁石、右側に黒い碁石を集めていく。 全ての白い碁石が全ての黒い碁石よりも左側にある状態になったらゲームは終了である。

実は、このゲームの最小手数はプログラムを書いて簡単に求めることができる。ゲームに飽きてしまったら、ぜひ挑戦してみてくれたまえ。

Input

入力は以下の形式で表される。

D
N₁
S₁₁ S₁₂ ... S_1N1
N₂
S₂₁ S₂₂ ... S_2N2
:
N_D
S_D1 S_D2 ... S_DND

ここでDはゲームの回数、N_iはi回目のゲームにおける碁石の数、S_ijはi回目のゲームにおいて左からj番目の碁石の色である。 S_ijは0ならば白、1ならば黒を表す。

Constraints

入力は以下の条件をすべて満たす。

• 1 <= D <= 100
• 1 <= i <= D を満たすすべての整数iについて、
  • 1 <= N_i <= 100
  • さらに1 <= j <= N_iを満たすすべての整数jについて、
    • S_ijはすべて{0, 1}のいずれか

Output

出力は、各ゲームごとに最小手数を1行で出力せよ。

Sample Input 1

1
5
1 0 0 1 0

Sample Output 1

4

説明のため、左の碁石から順に1〜5番と番号をつけることにする。 例えば、1手目で1番と2番、2手目で4番と5番、3手目で2番と3番、4手目で3番と4番を入れ替えることで、白い碁石が全て左側に寄り、黒い碁石が全て右側に寄る。これが最小手順なので、答えは4手となる。

Sample Input 2

3
8
1 1 0 1 1 0 1 1
3
0 0 1
12
1 0 1 0 1 0 1 0 1 0 1 0

Sample Output 2

6
0
21