Tree Weight Modification

In this problem, you are given a tree with n nodes numbered from 1 to n. The tree is rooted at node 1. Each node i has an initial weight a_i (a positive integer). You are allowed to change the weight of any node to any positive integer. The goal is to ensure that for every node that has at least two children, the product of the weights of any two of its children is not a perfect square.

Recall that an integer is a perfect square if it can be written as x² for some integer x. Equivalently, if every positive integer can be factored as b²⋅s, where s is square‐free (that is, no square number greater than 1 divides s), then the product of two numbers a and b is a perfect square if and only if their square‐free parts are equal.

Thus, for a node with at least two children, if any two children share the same square‐free part, then the product of their weights will be a perfect square. Your task is to determine the minimum number of nodes whose weights must be modified so that every node with two or more children satisfies the condition: the square‐free parts of the weights of its children are all distinct. You may choose the new weights arbitrarily (as long as they are positive integers) to achieve this.

inputFormat

The input consists of several lines:

1. The first line contains a single integer n (the number of nodes in the tree).
2. The second line contains n positive integers: a₁, a₂, ..., a_n, where a_i is the weight of node i.
3. The next n - 1 lines contain one integer each. For i = 2, 3, ..., n, the i-th of these lines contains a single integer p_i which denotes that there is an edge between node p_i (the parent) and node i. It is guaranteed that the tree is rooted at node 1.

outputFormat

Output a single integer: the minimum number of nodes that need to have their weights modified so that for every node having at least two children, the product of any two children’s weights is not a perfect square.

sample

3
1 1 1
1
1

1