小美和小猴决定玩一个数字游戏
小美在纸上写下 n 个数字 a_1,a_2,...,a_n ，小猴则会写下一个数字 q 。
由于小美最近复习离散数学，所以她想要和小猴玩一个有关于互质的游戏。一般来说，如果两个数 x 和 y 的最大公约数为 1 ，我们就说 x 和 y 是互质的。
具体来说，小美会询问小猴一共 m 个问题，每次询问，小美会问小猴一段连续的区间 l \sim r 内有多少个数与小猴所写下的数字 q 互质。
由于小美写的数字太多了，所以小猴想请求你的帮助，你能回答小美的问题吗?
第一行，包含三个整数 n,m,q 。
第二行，包含 n 个整数 a_1,a_2,...,a_n 。
接下来 m 行，每行两个整数 l,r ，表示这一次小美询问的区间
输出 m 行，每行一个整数，表示小美本次询问的区间
输入
5 3 2 1 2 3 4 5 1 3 2 4 1 5
输出
2 1 3
对于 80% 的数据: 1 <= n,m <= 2 * 10^3 ， 1 <= ai,q <= 10^9
对于 100% 的数据: 1 <= n,m <= 2 * 10^5 ， 1 <= ai,q <= 10^9