Sum Digits Until One

You are given a list of digit strings. For each value, repeatedly sum its digits until a single digit remains; return the mode, the single digit that occurs most frequently. On a tie, this site returns the larger digital root.

输入格式

The first line contains N (this site limits 1≤N≤200000), followed by N lines, each containing a non-negative decimal digit string. Leading zeros are allowed; signs are not. Each string has length ≤100000, and the total number of digits is ≤2000000.

输出格式

Output the mode; if several digital roots share the highest frequency, output the largest of them.

样例 1

输入：

3
1234
24
33

输出：

6

样例说明

Scan the digits, sum them, and take the digital root modulo 9, then count the frequencies; zero maps to 0 separately.