Description

数根是这样定义的：对于一个正整数m，将它的各个数位上的数字相加得到一个新数，如果这个数是一位数，我们就称之为m的数根，否则重复处理直到它成为一个一位数。
例如，m=34，3+4=7，7是一位数，所以7是34的数根。 再如，m=345，3+4+5=12，1+2=3，3是一位数，所以3是345的数根。
 对于输入n个正整数，输出其中数根最大的一个数。

Input Format

第一行一个正整数n。

第二行n个正整数，每个正整数以空格间隔。

Output Format

输出数根最大的一个数，如有多个数数根最大，则只输出第一个。

10
23 454 7 757 32 4 344 45454 111111 45

45

Hint

【样例1解释】

10个数的数根依次为5 4 7 1 5 4 2 4 6 9，9最大所以输出45

【数据范围约定】

对于70%的数据，1≤n≤10000，1≤m≤10^9

对于100%的数据，1≤n≤1500000，1≤m≤10^18

注意：输入数据很大，用scanf

</span>