Conformity Prize

Interview

Time limit1sMemory limit128 MB

Summary

Canonicalize each frosh's five courses, count how many frosh share each set, then output the total over all sets with the maximum count.

Level: Easy3 of 10
Topics: Hash map, Sorting, Implementation, Array
Solved: No attempts yet

Problem

First-year students (frosh) arriving at university have wildly different interests, as shown by the many different combinations of courses they want to take.

Administrators are uncomfortable with all this variety, so they decide to award a "conformity prize" to every frosh who picks one of the most popular course combinations. How many frosh win the prize?

Each frosh chooses exactly five distinct courses. The popularity of a combination is the number of frosh who chose exactly that same set of five courses. The order in which the courses are listed does not matter: two selections made of the same five course numbers are the same combination. A combination is most popular if no other combination has strictly higher popularity (that is, it attains the maximum popularity). Several combinations may be tied for most popular.

Input

The input consists of several test cases followed by a line containing $0$ .

Each test case begins with an integer $n$ , the number of frosh ( $1 \le n \le 10000$ ). Then $n$ lines follow; each line contains the course numbers of the five distinct courses selected by one frosh. Each course number is an integer between $100$ and $499$ inclusive.

Output

For each test case, output on a single line the total number of frosh who chose a most-popular combination. In other words, print the sum of the sizes of all combinations that attain the maximum popularity.

Examples1

Example 1

Input

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
0

Expected output

2
3