问题 B：公约数神庙

当大地陷入了混乱和分裂，一位智者带来了一本神秘的古老书籍。这本书上写着关于 $n$ 个古老神庙的秘密，每座神庙都藏有珍贵的宝物。这些神庙被分布在各种不同的地方，被认为是人类文明的遗产。

第 $i$ 座神庙有一个独特的权值 $a[i]$，代表着其中蕴含的智慧和力量。这些神庙之间有着一种神秘的联系：若 $i\le j$ 且 $gcd(a[i],a[j])>1$，那么你可以从神庙 $i$ 走到神庙 $j$。额外约定：

• 神庙 $i$ 能走到神庙 $i$
• $gcd(0,0)=0$

第一行包含两个整数 $n,q$，表示神庙的数量和询问的数量

第二行包含 $n$ 个整数 $a[1],a[2],...,a[n]$，表示每座神庙的权值

接下来 $q$ 行，每行包含两个整数 $(x,y)$，表示一次询问

$n,q\le 10^5, 0\le a[i]\le 1000, x\le y$

5 4
1 3 0 2 1
1 3
2 4
1 4
1 1

Fou
Shi
Fou
Shi