L. Pigeonhole Principle @ Ural Regional School Programming Contest 2019 @ Timus Online Judge

L. Pigeonhole Principle

Time limit: 0.5 second
Memory limit: 256 MB

Little Pete Dirichlet likes pigeons a lot. He comes to the dovecote everyday, puts pigeons into holes and counts how many pigeons there are in each hole.

One day he found n holes, and the dovecote had exactly n pigeons. Also, n was even. Pete put pigeons into holes so that each hole contains exactly one pigeon. “So beautiful!” — he had thought at first, but then looked carefully and saw this:

His inner perfectionist got upset, and he decided to change the orientation of some pigeons, so that they would sit in a nice pattern. Pete considers these two patterns nice:

the left half of pigeons looks in one direction, and the right half — in another direction;
pigeons alternate: all pigeons on even spots look in one direction, and all pigeons on odd spots — in another direction.

Find out the smallest amount of pigeons whose orientation needs to be changed to form a nice pattern.

Input

The first line contains one even integer n — the amount of pigeons (2 ≤ n ≤ 100).

Then, three lines of length 5n − 1 each follow. They describe n pigeons. Every pigeon takes up four characters in each of the three lines. Pigeons, oriented to the left and to the right respectively, are denoted like this:

                                 <@..            ..@>
                                 .OO=            =OO.
                                 ./\.            ./\.

Characters used are “.” (code 46), “/” (code 47), “<” (code 60), “=” (code 61), “>” (code 62), “@” (code 64), “O” (code 79), “\” (code 92). Each pair of adjacent pigeons are separated with a column of periods. It is guaranteed that lines contain nothing except for descriptions of pigeons and columns separating them.

Output

Output one number — the answer to the problem.

Samples

input	output
8 ..@>.<@...<@.....@>...@>...@>.<@...<@.. =OO...OO=..OO=.=OO..=OO..=OO...OO=..OO= ./\.../\.../\.../\.../\.../\.../\.../\.	4
4 ..@>...@>.<@.....@> =OO..=OO...OO=.=OO. ./\.../\.../\.../\.	1

Notes

In the first example he needs to rotate the first, the fourth and the last two pigeons, then the first half would look to the left, and right half — to the right.

In the second example he needs to rotate the first pigeon so they would alternate.

Problem Author: Kirill Borozdin
Problem Source: Ural School Programming Contest 2019