동전 뒤집기

N^2개의 동전이 N행 N열로 탁자 위에 놓여 있다. 각 동전은 앞면 H 또는 뒷면 T가 위를 향한다. 아래 그림은 N = 3인 경우의 한 상태를 보여준다.

<그림 1>

한 번의 작업으로 임의의 한 행 또는 한 열에 있는 N개의 동전을 모두 뒤집을 수 있다. 예를 들어 그림 1의 상태에서 첫 번째 열을 모두 뒤집으면 그림 2가 되고, 이어서 첫 번째 행을 모두 뒤집으면 그림 3이 된다.

<그림 2>	<그림 3>

그림 3에서는 뒷면이 위를 향한 동전이 2개이다. 그림 1의 상태에서 행이나 열 전체를 뒤집는 작업을 아무리 반복해도 뒷면 동전의 개수를 2개보다 작게 만들 수 없다.

초기 상태가 주어졌을 때, 행 또는 열 전체를 뒤집는 작업을 원하는 만큼 수행하여 만들 수 있는 뒷면 동전 개수의 최솟값을 구하라.

첫째 줄에 자연수 N이 주어진다. N은 20 이하이다.

둘째 줄부터 N개의 줄에 걸쳐 각 행의 동전 상태가 주어진다. 각 줄은 길이 N의 문자열이며, 왼쪽부터 차례대로 앞면은 H, 뒷면은 T로 표시한다. 문자 사이에 공백은 없다.

행 또는 열 전체를 뒤집는 작업을 수행한 뒤 만들 수 있는 뒷면 동전 개수의 최솟값을 출력한다.