题目背景

夏天快要到了，去兴绍奶龙山参加 ION5202 的 0p 决定探究奶龙山的性质。

题目描述

奶龙山内部存在复杂的奶龙山隧道，但是聪明的 0p 一眼就看出了 $n-1$ 条奶龙山隧道的结构是一颗树。其中任意两个隧道只在 $n$ 个休息点处相交，两两休息点之间都有路径联通，第 $i$ 个休息点有一个权值 $a_i$，对于每一个素数 $p$，若 $p\mid a_i$ 则说明 $p$ 公司参与了休息点建设。想要经过一个休息点，就必须和所有参与了休息点建设的公司搞好关系。

0p 有 $q$ 条心仪的路线，第 $i$ 条是从休息点 $u$ 走到休息点 $v$，对于每一条路线，0p 想知道，他需要与多少公司搞好关系才可以成功地走完这一条路线。

请注意算法常数对时间效率的影响。

输入格式

第一行，两个正整数 $n,q$。

第二行，共 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示一条树边。

接下来 $q$ 行，每行两个正整数 $u,v$，表示一条路线。

输出格式

输出共 $q$ 行，对于每一条路线，输出所求的答案。

3 1
7 2 1
1 2
1 3
2 3

2

10 7
9 9 8 2 4 4 3 5 3 97
1 2
1 3
3 4
5 2
6 4
7 5
9 1
10 2
3 8
4 5
2 3
4 6
2 4
1 2
4 10
1 1

2
2
1
2
1
3
1

提示

对于 $20\%$ 的数据，满足 $n,q\leq 100$。

对于 $70\%$ 的数据，满足 $n,q\leq 1000$。

对于 $100\%$ 的数据，满足 $1\leq n,q\leq 5\times 10^4$，$1\leq a_i\leq 10^5$，$1\leq u,v\leq n$，保证给出的树合法。