최고의 치킨 요리

Fouad와 심사위원들, 그리고 대회 운영진은 배가 고파서 식당에 갔다. 이 식당은 꼬치에 치킨 큐브를 꿰어 내는데, 각 꼬치에는 N개의 치킨 큐브가 있고 i번째 큐브에는 그 큐브를 익힐 때 쓴 향신료 배합을 나타내는 정수 Ai가 적혀 있다. 연속한 큐브 몇 개는 그 향신료 배합들의 최대공약수(GCD)가 정확히 D일 때 Fouad의 기준에서 맛있다고 한다.

Fouad는 꼬치의 여러 부분을 맛보고 싶어서 심사위원들에게 계속 질문을 던지는데, 각 질문은 정수 세 개 L, R, D로 이루어지고, 범위 AL, AL+1, ···, AR 안에서 향신료 배합의 GCD가 D인 연속한 부분이 몇 개인지, 즉 gcd(Ai, Ai+1, ···, Aj) = D이고 L ≤ i ≤ j ≤ R인 모든 쌍 (i, j)의 개수를 알고 싶어 한다.

심사위원들은 문제를 풀지 않고 쉬면서 먹고 싶어서, 이 문제를 대신 풀어 달라고 당신에게 부탁했다. 풀 수 있겠는가?

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다.

각 테스트 케이스는 정수 두 개 N과 Q(1 ≤ N ≤ 105, 1 ≤ Q ≤ 5 · 104)가 있는 줄로 시작하며, N은 꼬치에 있는 치킨 큐브의 수, Q는 Fouad가 물을 질문의 수이다.

다음 줄에는 N개의 정수 A1, ···, AN(1 ≤ Ai ≤ 106)이 주어지며, Ai는 i번째 치킨 큐브를 익힐 때 쓴 향신료 배합을 나타낸다.

그다음 Q개의 줄이 주어지고, 각 줄에는 공백으로 구분된 정수 세 개 L, R, D(1 ≤ L ≤ R ≤ N, 1 ≤ D ≤ 106)가 주어져 질문을 나타낸다.

각 테스트 케이스마다 질문 하나당 한 줄씩, 주어진 범위 [L, R] 안에서 향신료 배합의 GCD가 D인 연속한 부분의 개수를 출력한다.

여러 인자의 최대공약수는 gcd(x1, x2, ···, xn) = gcd(gcd(x1, ···, xn−1), xn)이라는 식에 따라 재귀적으로 계산한다.