小 A 和小 F 决定玩一个数字游戏。
小 A 在纸上写下 n 个数字 a1,a2,...,an ，小 F 则会写下一个数字 q。
由于小 A 最近在复习离散数学，所以他想和小 F 玩一个有关于互质的游戏。一般来说，如果两个数 a 和 b 的最大公约数为 1，我们就说 a 和 b 是互质的，简记为 a⊥b。 
具体来说，小 A 会询问小 F 一共 m 个问题，每次询问，小 A 会问小 F 一段连续的区间 l∼r 内有多少个数与小 F 所写下的数字 q 互质。
由于小 A 写下的数字太多了，所以小 F 想请求你的帮助，你能回答小 A 的问题吗？

第一行输入三个整数 n,m,q。 表示小 A 写下的数字个数、小 A 进行的询问个数和小 F 写下的数字。
第二行输入 n 个整数，表示 a1,a2,...,an
接下来 m 行，每行两个整数 l,r。表示这一次小 A 询问的区间。

输出 m 行，每行一个整数，表示小 A 本次询问的答案。

样例一解释：
所有的奇数都与 2 互质, 而 1 ∼ 3 之中有两个奇数，故答案为 2。剩下两个询问同理。
样例二：
输入：
6 4 6
3 4 12 2 1 8
1 3
2 5
3 4
1 6
输出：
0
1
0
1


1 <= n <= 100000
1 <= m <= 1000000
1 <= ai, q <= 10000 

信息未来