【问题描述】
Richie非常喜欢质数，甚至他想为黎曼猜想奋斗终身。BUT如果素数之谜被解开，那么基于素数的RSA加密系统也将不复安全。科学真是一把双刃剑。
现在给出一个长度为n的数列 a1 a2 a3 ... an，以及m组询问 (li ri ki)，该三元组用来表示 求区间 [li ri]中有多少数在该区间中的出现次数与 ki互质。
【输入形式】
第一行，两个正整数n m。
第二行，n 个正整数 ai 描述这个数列。
接下来 m行，每行三个正整数 li ri ki，描述一次询问。
数据范围与数值大小规定如下 1≤nm≤50000 ，1≤ai≤n，1≤li≤ri≤n，1≤ki≤n
【输出形式】
输出 m行，每行输出每次询问的答案。
【样例输入】
10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3
【样例输出】
0
2
1
1
0
【样例说明】
【评分标准】
| 难度等级： | 0 |
| 总通过次数： | 0 |
| 总提交次数： | 85 |