Junji has found a beautiful tree lying on the ground, and he wants to take it home to beautify his house. However, he only plans on taking a segment of the tree because he has aichmophobia and too many branches scares him.

The tree has connection points. Each connection point has a *strength*, . A *good* segment is a segment of the tree where every connection point on the segment has a *strength* that has a solution to for some **integer **. A segment of the tree is a path of the tree where every connection point is used at most once. Junji wants the **longest** *good* segment to bring home to beautify his house. Note that the **longest** *good* segment *may* be the entire tree, in which case he will take the entire tree home.

#### Input Specification

The first line will contain the integer , the number of connection points.

The second line will contain integers, , the *strength* of each connection point.

The next lines will each contain two integers , meaning that connection point and connection point are connected by a single branch.

It is guaranteed that there is exactly one path between any two connection points.

#### Output Specification

Output the number of connection points in the **longest** *good* segment in the tree.

#### Constraints

##### Subtask 1 [10%]

All connection points satisfy the constraint for some integer .

##### Subtask 2 [20%]

##### Subtask 3 [70%]

No additional constraints.

#### Sample Input 1

```
7
6 2 30 20 90 42 2
1 2
2 3
3 4
3 5
2 6
2 7
```

#### Sample Output 1

`4`

#### Sample Input 2

```
8
2 9999999900000000 3 3 3 3 3 1
1 2
1 3
3 4
4 5
3 6
2 7
2 8
```

#### Sample Output 2

`2`

## Comments