B"Eugene got Burenka an array a of length n of integers from 1 to m for her birthday. Burenka knows that Eugene really likes coprime integers (integers x and y such that they have only one common factor (equal to 1 )) so she wants to to ask Eugene q questions about the present. Each time Burenka will choose a subsegment a_l, a_{l + 1}, ldots, a_r of array a , and compute the product of these numbers p = a_l cdot a_{l + 1} cdot ldots cdot a_r . Then she will ask Eugene to count the number of integers between 1 and C inclusive which are coprime with p . Help Eugene answer all the questions! In the first line of input there are four integers n , m , C , q ( 1 <= q n, q <= q 10^5 , 1 <= q m <= q 2 cdot 10^4 , 1 <= q C <= q 10^5 ) -- the length of the array a , the maximum possible value of a_{i} , the value C , and the number of queries. The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= q a_{i} <= q m ) -- the array a . In the next q lines the queries are given. Each query consists of two integers l and r ( 1 <= q l <= q r <= q n ). Print q integers -- the answers to Burenka's queries. Here's an explanation for the example: "...