Chef and The Divisibility Queries

The Chef is given a sequence of N integers A1, A2, ..., AN. He has to process Q queries on the above sequence. Each query is represented by three integers: - L R K => report cardinality of { i : K divides Ai, L ≤ i ≤ R }. In other words, how many integers in the subsequence starting at Lth element and ending at Rth element are divisible by K. Input The first line of the input contains two