Stacks of coins

A collection of gold and silver coins, all of the same size, is arranged in (n) columns on a table. The columns may vary in height.

In a single move, you can swap two coins from different columns, as long as they are at the same height from the table.

A column is considered monochrome if it contains coins of only one color (either all silver or all gold). Your task is to determine the maximum number of monochrome columns that can be formed by performing any number of the allowed moves.

Input

The first line of input contains a single integer (n) ((1 $\le$ n $\le$ 1000000)) — the number of columns on the table.

Each of the next (n) lines consists of the characters "G" and "S", representing one column. The character "G" stands for a gold coin, and "S" stands for a silver coin. The coins are listed from the bottom (closest to the table surface) to the top of the column.

The total number of coins on the table does not exceed (1000000).

Output

Output a single integer — the maximum number of monochrome columns that can be formed from the initial arrangement using the allowed moves.

Examples