题目内容

产业园里有 $n$ 个站点，用 $n-1$ 条双向链路连成一棵树，站点编号为 1 到 $n$。站点 $i$ 的信号强度为 $a_i$。一条简单路径的耦合度定义为路径上所有站点信号强度的最大公因数 $\gcd$；若路径只含一个站点，则耦合度就是该点强度。路径 $u \to v$ 与 $v \to u$ 视为同一条，单点路径 $u \to u$ 也要计入。请统计耦合度为偶数的简单路径条数。

约束：$1 \le n \le 200000$，$1 \le a_i \le 1000000$。

输入描述

第一行一个整数 $n$，表示站点数。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示信号强度。