Teto's Song#12445
Sign in

Teto's Song

1 second
256 megabytes
Easy

Teto is writing a short song.

The song has lines. Each line is written as a string of length exactly , and every character is either "a" or "b".

Before finishing the song, Teto may edit each line independently. For each line, she may perform the following operation at most once:

Choose one character in this line and change it to the other character. That is, "a" becomes "b", and "b" becomes "a".

Teto wants as many lines as possible to become exactly the same. These equal lines will form the chorus of the song.

Determine the maximum possible number of equal lines Teto can obtain.

Input

The first line contains one integer (1 \le n \le 2 \cdot 10^5) — the number of lines in the song.

Each of the next lines contains one string s_i (|s_i| = 3), consisting only of characters "a" and "b".

Output

Output a single integer — the maximum possible number of equal lines.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the example, Teto can make lines equal to "aaa":

  • "aaa" is already equal to "aaa";

  • "aab" can be changed to "aaa";

  • "aba" can be changed to "aaa";

  • "baa" can be changed to "aaa".

So the maximum possible number of equal lines is .

Scoring

  1. Subtask ( points): n \le 3.

  2. Subtask ( points): n \le 100.

  3. Subtask ( points): No additional constraints.