Greatest Chicken Dish

Fouad, the ACPC judges, and the organizers were hungry, so they went to a restaurant. This restaurant makes chicken cubes on seekh (skewers), and each seekh has N chicken cubes where the ith cube has an integer Ai that represents the mixture of spices used to cook that cube. A set of successive cubes is delicious from Fouad's perspective when the greatest common divisor (GCD) of their spice mixtures is exactly D.

Fouad wants to try many sub-parts of the seekh, so he keeps asking the judges queries. Each query consists of three integers L, R, and D, and he wants to know the number of consecutive sub-parts of the seekh in the range AL, AL+1, ..., AR whose spice mixtures have GCD equal to D, that is, the count of all pairs (i, j) such that gcd(Ai, Ai+1, ..., Aj) = D and L ≤ i ≤ j ≤ R.

The judges want to relax, eat, and not solve problems, so they asked you to solve this problem for them. Can you solve it?

The first line of the input contains a single integer T, the number of test cases.

Each test case begins with a line containing two integers N and Q (1 ≤ N ≤ 105, 1 ≤ Q ≤ 5 · 104), where N is the number of chicken cubes on a seekh and Q is the number of queries Fouad will ask.

Then a line follows containing N integers A1, ..., AN (1 ≤ Ai ≤ 106), where Ai represents the mixture of spices used to cook the ith chicken cube.

Then Q lines follow, each containing three space-separated integers L, R, and D (1 ≤ L ≤ R ≤ N, 1 ≤ D ≤ 106), giving the queries.

For each test case, print one line per query containing the number of consecutive sub-parts of the seekh in the given range [L, R] whose spice mixtures have GCD equal to D.

The greatest common divisor of multiple arguments is computed recursively according to gcd(x1, x2, ..., xn) = gcd(gcd(x1, ..., xn−1), xn).