Byteland 彩票组织举办的最受欢迎的游戏之一是“Huge blend”。游戏的规则很简单：从一个装有固定数量球的容器中（每个球上都标有一个自然数），选出若干个球。下一步是计算所选球上所有数字的乘积。该乘积即为中奖号码。猜对该数字的人将赢得大奖。在抽奖之前，已知会有多少个球参与抽奖，球上的数字也是已知的。但不知道会选出多少个球——可能是全部，也可能只有一个。

ByteGuy 一直想赢得“Huge blend”，然而多年的徒劳尝试让他开始思考获胜的几率。他决定计算 $n$ ——所有可能的抽奖结果之和。不幸的是，ByteGuy 的计算机在计算过程中过热了，所以他请求你帮他计算一个更简单的值 $F(n)$，其中 $F$ 是一个定义如下的函数：

• $F(k) = k$, $k \le 9$
• $F(k) = F(\text{k 的所有数字之和})$, $k \ge 10$

例如：$F(9) = 9$, $F(123) = 6$, $F(9876) = F(30) = 3$。

编写一个程序：

• 从标准输入读取数字 $l$（参与抽奖的球的数量）以及 $l$ 个自然数 $w_{1}, w_{2}, \ldots, w_{l}$（球上印的数字），
• 计算 $F(n)$ 的值，其中 $n$ 是所有可能的抽奖结果之和，
• 将答案写入标准输出。

输入格式

标准输入的第一行包含一个自然数 $l$ ——参与抽奖的球的数量，$1 \le l \le 10^{6}$。第二行包含 $l$ 个自然数 $w_{m}$，$0 \le w_{m} \le 10^{8}$ ——球上印的数字。数字之间用单个空格分隔。

输出格式

输出一个整数到标准输出。该整数应为 $F(n)$ 的值。

样例

输入 1

3
10 13 12

输出 1

3