You are given a tree $T$ of size $N.$ You are given a $2$D array $E$ of size $M,$ where there exists an edge between $E[i][0]$ and $E[i][1]$ for all $1iM.$

You are also given an array $A$ of size $N,$ where the node $U$ has a value $.$

A path $P$ is called a good path if the greatest common divisor$($GCD$)$ of all of the values present on the path $P$ is equal to $1.$ Two paths $P_1,P_2$ are considered the same if they have the same number of nodes and each node $x$ of path $P_1$ belongs to $P_2.$

Find the total number of possible good paths present in $T.$

Note:

The path $(U,U)$ is valid for all nodes $U.$

Input Format

The first line contains an integer, $N,$ denoting the number of elements in $A.$

The next line contains an integer, $M,$ denoting the number of rows in $E.$

The next line contains an integer, two, denoting the number of columns in $E.$