Let's observe any array of natural numbers ~A~ and the GCD (greatest common divisor) of each prefix in the array, ~P~. For example:

~i~	1	2	3	4	5	6	7	8
~A_i~	216	144	96	96	120	560	9	8
~P_i~	216	72	24	24	24	8	1	1

Let's observe the two adjacent values ~P_i~ and ~P_{i+1}~. The following properties hold:

• ~P_i~ is divisible by ~P_{i+1}~.
• ~P_i \ge P_{i+1}~. In the case that ~P_i \ne P_{i+1}~, then it holds ~P_i \ge 2P_{i+1}~, which is why the value ~P_i~ will change ~\log_2 10^9~ times at most.

We conclude that array ~P~ can be written in a different way, so that we group all the prefixes with the same GCD, as an array of at most ~\mathcal O(\log 10^9)~ pairs of numbers ~(g, d)~ where ~g~ represents one of the values ~P_i~, and ~d~ represent the number of appearances of that value in array ~P~. For example, the array ~P~ from the above example can be written as: ~\{(216, 1), (72, 1), (24, 3), (8, 1), (1, 2)\}~. Analogously, we can write the GCD of all suffixes of array ~A~.

We will solve this task using a segment tree where we will store the following data for each interval:

• GCD of all prefixes ~P~ (in the above mentioned form, so as an array of pairs ~(g, d)~),
• GCD of all suffixes ~S~ (also in the above mentioned form), and
• The number of interesting contiguous subsequences in that interval, ~count~.

In order to apply the tournament tree data structure on this task, we need to define how we can determine new data for the union of intervals, based on the aforementioned data for two adjacent intervals. Let there be two adjacent intervals ~L~ and ~R~. Based on the GCD of all prefixes ~L.P~ and ~R.P~, let's try to determine the GCD of all prefixes ~C.P~ (where ~C~ represents the union of intervals ~L~ and ~R~). Array ~C.P~ is calculated in the following way:

• ~g(C.P_i) = g(L.P_i)~ for ~1 \le i \le len(L.P)~
• ~g(C.P_i) = \gcd(g(L.P_{len(L.P)}), g(R.P_{i-len(L.P)}))~, for ~len(L.P)+1 \le i \le len(L.P)+len(R.P)~

We can notice that in some cases it will be possible to additionally group some elements in the array ~C.P~ by values ~g(C.P)~, and that the length of the total array is never going to be larger than ~\log_2 10^9~. The complexity of determining this array is ~\mathcal O(\log 10^9)~, and analogously, we can determine the array ~C.S~ that represents the GCD of all suffixes of interval ~C~.

All that is left to determine is how we can calculate the number of interesting subsequences in the interval ~C~ (~C.count~). These values will be equal to the sum of values ~L.count~, ~R.count~ and the number of interesting subsequences that are in both intervals ~L~ and ~R~. Let ~L~ correspond to the interval ~[l, m]~, and ~R~ to the interval ~[m+1, r]~. Let's observe the smallest ~p~ from the interval ~L~, for which a ~q~ exists from the interval ~R~ such that it holds that the subsequence ~[p, q]~ is interesting, and the subsequence ~[p, q+1]~ is not. The GCD of the subsequence ~[p, q]~ can be calculated as the largest common divisor of the GCD-suffix until position ~p~ in array ~L.S~ and the GCD-prefix until position ~q~ in array ~R.P~. However, we should notice one more thing: as we increase ~p~, so will the value ~q~ either remain the same or increase by a positive number. Therefore, the number of interesting subsequences contained in both intervals ~L~ and ~R~ can be calculated using the two-pointer technique, ~p~ that will iterate over array ~L.S~ and ~q~ that will iterate over array ~R.P~. The complexity of this approach is ~\mathcal O(len(L.S)+len(R.P))~, i.e. ~\mathcal O(\log 10^9)~.

The total complexity of the joining is ~\mathcal O(\log 10^9)~, so the total complexity of the algorithm is ~\mathcal O((N+Q) \log N \log 10^9)~.