这是一个跳跃游戏。在游戏中你可以跳到任意位置，其中有 $n$ 个点：$1 , 2 , 3, \cdots , n$，跳到那里会有奖励分数 $a_1 , a_2 , \cdots , a_n$。
显然，这个游戏很简单，$\texttt{MhxMa}$ 没过多久就获得了所有分数，于是改进了代码，添加了经验值这个参数。
对于有奖励分数的 $n$ 个点，若从点 $x$ 跳到点 $y$，会获得经验值 $\operatorname{score}_{x , y}(1\le x\le y\le n)$：
$$\operatorname{score}_{x,y}=\begin{cases}\operatorname{len} & \operatorname{gcd}(a_x , a_{x+1} , \dots , a_y)=2 , \operatorname{len \ mod} 2 = 0 \\ \operatorname{len} &\gcd(a_x , a_{x + 1} , \dots , a_y)=3 , \operatorname{len \ mod} 2 = 1\\ 0 & \operatorname{others} \end{cases}$$
其中，$\operatorname {len}$ 表示区间的长度，即 $y-x+1$。
**对于每一对位置 $(x,y)$，多次跳跃只会获得一次经验值。**
为了向 $\texttt{MhxMa}$ 展现你的编程实力，你决定写一个代码算出这个游戏能刷到的最大经验值。
## Input
输入共两行。
输入第一行包含一个整数 $n$。
第二行包含 $n$ 个整数 $a_i$。
## Output
输出一个整数，表示答案。
[samples]
## Background
本来可怜的 $\texttt{MhxMa}$ 想出这道题，但是已经被 $\texttt{Ferm\_Tawn}$ 抢了，此时 $\texttt{MhxMa}$ 坐在电脑面前，看着马上要造好的数据，想象着自己的题难倒一大片选手的梦想破灭了。
## Note
**请使用较快的读入方式。**
### 样例解释 #1
$\operatorname{score_{2 , 2}}= 1$。
$\operatorname{score_{2 , 4}}= 3$。
$\operatorname{score_{3 , 5}}= 3$。
$\operatorname{score_{4 , 4}}= 1$。
$1+3+3+1=8$。
### 样例解释 #2
$\operatorname{score_{1 , 2}}= 2$。
$\operatorname{score_{1 , 4}}= 4$。
$\operatorname{score_{2 , 3}}= 2$。
$\operatorname{score_{2 , 5}}= 4$。
$\operatorname{score_{3 , 4}}= 2$。
$\operatorname{score_{4 , 5}}= 2$。
$2+ 4 + 2 + 4 + 2 + 2 = 16$。
------------
### 数据规模与约定
**本题采用捆绑测试**。
- Subtask 0（20 pts）：$n \le 10^2$。
- Subtask 1（10 pts）：$n \le 2 \times 10^3$。
- Subtask 2（20 pts）：$n \le 10^4$。
- Subtask 3（50 pts）：$n \le 6 \times 10^5 $。
对于所有测试数据，$1 \le n \le 6 \times 10^5$，$1 \le a_i \le 10^7$。