Count GCD Pairs in Subarrays

You are given an array (A) of (N) integers and (Q) queries. For each query, you are provided with three integers (L), (R), and (K). Your task is to count the number of pairs of indices ((i, j)) with (L \leq i < j \leq R) such that (\gcd(A[i], A[j]) \geq K). Here, (\gcd(a,b)) denotes the greatest common divisor of (a) and (b).

For example, consider (N=5), (A=[10, 15, 25, 20, 30]) and (Q=3) queries:

1. Query: ((1, 3, 5)) (\Rightarrow) Count pairs from indices 1 to 3 with (\gcd \geq 5).
2. Query: ((2, 5, 10)) (\Rightarrow) Count pairs from indices 2 to 5 with (\gcd \geq 10).
3. Query: ((1, 5, 15)) (\Rightarrow) Count pairs from indices 1 to 5 with (\gcd \geq 15).

The answer for the sample query would be: [3, 2, 1].

inputFormat

The input is given from (stdin) in the following format:

• The first line contains two integers (N) and (Q) separated by a space.
• The second line contains (N) space-separated integers representing the array (A).
• The next (Q) lines each contain three space-separated integers (L), (R), and (K), describing a query.

It is guaranteed that (1 \leq L \leq R \leq N).

outputFormat

For each query, output a single integer on a new line representing the number of pairs ((i, j)) in the subarray ([L, R]) satisfying (\gcd(A[i], A[j]) \geq K).## sample

5 3
10 15 25 20 30
1 3 5
2 5 10
1 5 15

3
2
1