Lazy Intern

Deepanshu applied for an internship last month and went through multiple rounds. After all this process, he got selected for the internship and is very excited. He went to the office happily and received the orientation. He got to know that he will be working under the Tech Manager. On the first day at the office, he realized that he has to walk a lot as there are a lot of discussions required and meetings are set every now and then. The manager's cubicle M is located far from where he is seated and he has to take a long path to reach him and he is very lazy for this.

The office is divided into two partitions and is separated by space between them. There are N rows of cubicles with four cubicles in each row of partition. All the vacant cubicles are marked with V and all the occupied cubicles are marked with O. There is a distance of one unit between the two rows of cubicles and there is a distance of two units between the two partitions. Between the cubicles in a row of a partition, there is no space or distance.

A representation of the office is provided below with 8 rows of cubicles.

Deepanshu is very lazy and he wants to cover as minimum as possible distance to reach the Manager's row in the partition where Manager's cubicle M is located. The limitation is that the movement can be only horizontally or vertically. Deepanshu wants to know the minimum distance he has to cover to reach the Manager's row in the partition where Manager's cubicle M is located and he will figure out the vacant cubicle on his own. He is busy with the work and needs your help to determine the minimum distance he has to cover. Can you help him?

Input Format

The first line of input consists of a single integer N, representing the number of rows in the office.

Next N lines contain the representation of the view plan of cubicles in the office.

Note: Space between partitions is represented with space at the location.


1<= N <=1000

Output Format

Print the required output in a separate line.

Sample TestCase 1

import java.util.*;

public class CandidateCode {
static Location manager;

public static void main(String[] args) {
Scanner sc = new Scanner(;
int n = sc.nextInt();

List<Location> vacant = new ArrayList<>();

for (int i = 0; i < n; i++) {
String row = sc.nextLine().replace(" ", "");
if (row.contains("M")) {
manager = new Location(i, row.indexOf('M'));
for (int j = 0; j < 8; j++) {
if (row.charAt(j) == 'V') vacant.add(new Location(i, j));

int ans = n + 1;
do {
int temp = 0;
Location closestVacantRow = -> Math.abs(v.row - manager.row))).get();
if (closestVacantRow.col > 3 && manager.col > 3 && closestVacantRow.row == manager.row) {
ans = 0;
} else if (closestVacantRow.col < 4 && manager.col > 3) {
temp += Math.abs(manager.row - closestVacantRow.row) + 2;
} else if (closestVacantRow.col > 3 && manager.col < 4) {
temp += Math.abs(closestVacantRow.row - manager.row) + 2;
} else {
temp += Math.abs(manager.row - closestVacantRow.row);
if (temp < ans) {
ans = temp;
} while (vacant.size() > 0);

static class Location {
int row;
int col;

public Location(int row, int col) {
this.row = row;
this.col = col;