Statement

For some k > 1, we say that the sequence of integers v = [v_1, v_2, … v_k] is good if v_i is divisible by i for every i from 1 to k. You are given an integer sequence A = [A_1, A_2, …, A_N] of length N and Q queries of the form l_i, r_i, which represent the range of values [A_l_i, A_l_i+1, …, A_r_i] from the sequence. For each query compute the number of subintervals of the given range which are good sequences (each subinterval is considered as an independent sequence, indexed from 1).