After hearing about the recent gold discovery in Belgium, you decide to travel to Brussels to make some profits.

Minutes after landing at the Brussels International Airport, you find yourself walking along a lonely road that seems to lead nowhere. Just as you start to reconsider your life choices, you enter a crossroads that separates ~4~ different areas of land. A sign reads: "You may only explore a single quadrant of land if you're looking for gold." Luckily, you brought your gold map of this exact plot of land. The map has ~2N~ rows and ~2N~ columns, divided evenly into four quadrants. The quadrant order is as follows:

Every character on the gold map consists of either d for dirt and g for gold. Your task is to output the number of the quadrant that has the most gold.

Input Specification

First line consists of a single integer ~N~ ~(1 \le N \le 20)~. This represents the width and height of a quadrant of the gold map.

The next ~2N~ lines consist of ~2N~ characters each. These are the contents of your gold map.

Output Specification

The number of the quadrant that will bring you the most gold. Break ties by outputting the quadrant that has both the most gold and the lowest number.

Sample Input

3
ddddgg
ddgddd
dddddd
gggddd
ddddgd
gggggg

Sample Output

3

Explanation

The bottom left quadrant, quadrant ~3~, has ~6~ gold bars. This is more than any other quadrant.