Eugene 为 Burenka 准备了一个数组 $$$a$$$,长度为 $$$n$$$,整数从 $$$1$$$ 到 $$$m$$$ 为她的生日礼物。 Burenka 知道尤金真的很喜欢互质整数(整数 $$$x$$$ 和 $$$y$$$ 使得它们只有一个公因数(等于 $$$1$$$)),所以她想问尤金 $$$q$$$ 有关现在的问题。
每次 Burenka 都会选择数组 $$$a$$$ 的一个子段 $$$a_l, a_{l + 1}, \ldots, a_r$$$,并计算这些数字的乘积 $$$p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r$$$。然后她会要求尤金计算 $$$1$$$ 到 $$$C$$$ 之间与 $$$p$$$ 互质的整数的数量。
帮助尤金回答所有问题!
输入
输入的第一行有四个整数 $$$n$$$, $$$m$$$, $$$C$$$, $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$, $$$1 \leq m \leq 2\cdot 10^4$$$, $$$1 \leq C \leq 10^5$$$) — 数组 $$$a$$$ 的长度、$$$a_{i}$$$ 的最大可能值、值 $$$C$$$ 以及查询数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq m$$$) — 数组 $$$a$$$ 。
在接下来的 $$$q$$$ 行中给出了查询。每个查询由两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) 组成。
输出
打印 $$$q$$$ 整数——Burenka 查询的答案。
示例
输入 #1
5 5 5 3 1 2 3 2 5 1 1 2 4 4 5
输出 #1
5 2 2
注意
以下是示例的解释:
1. 在第一个查询中,乘积等于 $$$1$$$,它与 $$$1,2,3,4,5$$$ 互质。
2. 在第二个查询中,乘积等于 $$$12$$$,它与 $$$1$$$ 和 $$$5$$$ 互质。
3. 在第三个查询中,乘积等于 $$$10$$$,它与 $$$1$$$ 和 $$$3$$$ 互质。