D. Eduardo Looking for Juan (Easy Version)
time limit per test
6 с
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference is that, $$$L = \inf$$$.

at lasteth we meeteth mine own boss juan
— Eduardo, Eduardo Looking for Juan

Eduardo has been looking for Juan for a long time, he finally found out that Juan is on some mountain The Horse Land but before he heads looking for him there he asked Ahmad for help, but he is too busy so it's your responsibility to help him.

Eduardo knows that The Horse Land is $$$n$$$ lands connected by $$$n - 1$$$ roads and there is a unique path between every two lands.

Furthermore, each land has a height $$$a_i$$$, Eduardo will travel from $$$u$$$ to $$$v$$$, but he can only do that if the multiplication of the height of the nodes on the way is a perfect square.

In a formal way let $$$p_1, ..., p_k$$$ the lands in the simple path from $$$u$$$ to $$$v$$$, where $$$p_1 = u$$$ and $$$p_k = v$$$, $$$\prod_{i=1}^{k} a_{p_i}$$$ should be a perfect square.

Eduardo hates surprises, so he will ask you about $$$q$$$ scenarios:

  • $$$u$$$ $$$v$$$: what is the minimum number of operations so that the multiplication on the simple path from $$$u$$$ to $$$v$$$ is a perfect square? In one operation, you can choose a land $$$i$$$ and multiply its height by some number $$$1 \leq x \leq L$$$.
Input

The first line contains a single integer $$$n$$$ $$$(2 \leq n \leq 10^6)$$$ – the number of lands.

The second line contains $$$n$$$ integers $$$(1 \leq a_i \leq 70)$$$ – the heights of the lands.

The next $$$n - 1$$$ lines describes the roads, the $$$i_{th}$$$ line contains two integers $$$u$$$ $$$v$$$ meaning there is a two-way road between $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$.

The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 5\times10^5)$$$ – the number scenarios.

The next $$$q$$$ lines each contains two integers $$$u$$$ $$$v$$$ $$$(1 \leq u, v \leq n)$$$.

Output

Print $$$q$$$ lines, each line is the answer to the $$$i_{th}$$$ scenario.

Example
Input
6
5 4 50 40 10 2
1 5
1 2
4 3
3 2
5 6
6
2 2
1 6
6 5
3 4
3 1
4 1
Output
0
0
1
1
1
0