Description

小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,...,a_n]$ 。

小杨想知道有多少对 $<l,r>(1 \leq l \leq r \leq n)$ 满足 $a_l \times a_{l+1} \times ... \times a_r$ 为完全平方数。

一个正整数 $x$ 为完全平方数当且仅当存在一个正整数 $y$ 使得 $x=y \times y$ 。

Input Format

第一行包含一个正整数 $n$ ，代表树的节点数。

第二行包含 $n$ 个非负整数 $a_1,a_2,...,a_n$ ，其中如果 $a_i=0$ ，则节点 $i$ 的颜色为白色，否则为黑色。

之后 $n-1$ 行，每行包含两个正整数 $x_i,y_i$ ，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边。

Output Format

输出一个整数，代表满足要求的 $<l,r>$ 数量。

5
3 2 4 3 2

2

Hint

样例解释

满足条件的 $<l,r>$ 有 $<3,3>$ 和 $<1,5>$ 。

数据范围

对于全部数据，保证有 $1 \leq n \leq 10^5 , 1 \leq a_i \leq 30$ 。

Source

GESP七级202406