Given N natural numbers $a_1,a_2....a_N$ and two weird functions $f(x)$ and $g(x)$.

$g(x) =$ sum of digits of x

$f(x) =1 + (\sum \limits_{i=1}^x g(a_i))$%$9 - g(\sum \limits_{i=1}^x a_i)$%9 if x % $(k*k) = 0$, $k \in \mathbb{N}$ and $k \ne 1$

$f(x) = 0$ otherwise.

Your task is to find the value of $\sum\limits_{i=1}^N f(i)$

Input:

First line of input contains a single integer N

Next N lines contains the natural numbers $a_1, a_2, .. a_N$

Output:

Output a single integer containing the required answer.

Constraints:

$1\le N \le 2*10^7$

$1\le a_i \le 10^{10000}$