CF1946F Nobody is needed

Oleg received a permutation $ a $ of length $ n $ as a birthday present. Oleg's friend Nechipor asks Oleg $ q $ questions, each question is characterized by two numbers $ l $ and $ r $ , in response to the question Oleg must say the number of sets of indices $ (t_1, t_2, \ldots, t_k) $ of any length $ k \ge 1 $ such that: - $ l \le t_i \le r $ for each $ i $ from $ 1 $ to $ k $ . - $ t_i < t_{i+1} $ for each $ i $ from $ 1 $ to $ k-1 $ . - $ a_{t_{i+1}} $ is divisible by $ a_{t_i} $ for each $ i $ from $ 1 $ to $ k-1 $ . Help Oleg and answer all of Nechipor's questions.

Each test consists of several sets of input data. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of sets of input data. The description of the sets of input data follows. The first line of each set of input data contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 10^6 $ ) — the length of the permutation and the number of Nechipor's questions. The second line of each set of input data contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the permutation $ a $ itself. In each of the next $ q $ lines of each set of input data, there are two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) — the next question of Nechipor. It is guaranteed that the sum of the values of $ n $ and the sum of the values of $ q $ over all test cases does not exceed $ 10^6 $ .

For each set of input data, output the answers to all of Nechipor's questions.

All suitable arrays in the first set of input data: ( $ 1 $ ), ( $ 2 $ ), ( $ 3 $ ), ( $ 4 $ ), ( $ 5 $ ), ( $ 6 $ ), ( $ 7 $ ), ( $ 8 $ ), ( $ 1, 3 $ ), ( $ 1, 6 $ ), ( $ 1, 7 $ ), ( $ 1, 6, 7 $ ), ( $ 2, 3 $ ), ( $ 2, 4 $ ), ( $ 2, 5 $ ), ( $ 2, 6 $ ), ( $ 2, 7 $ ), ( $ 2, 8 $ ), ( $ 2, 6, 7 $ ), ( $ 6, 7 $ ). All suitable arrays in the fourth set of input data: ( $ 1 $ ), ( $ 2 $ ), ( $ 3 $ ), ( $ 4 $ ), ( $ 5 $ ), ( $ 6 $ ), ( $ 7 $ ), ( $ 8 $ ), ( $ 1, 2 $ ), ( $ 1, 3 $ ), ( $ 1, 4 $ ), ( $ 1, 5 $ ), ( $ 1, 6 $ ), ( $ 1, 7 $ ), ( $ 1, 8 $ ), ( $ 1, 2, 4 $ ), ( $ 1, 2, 6 $ ), ( $ 1, 2, 8 $ ), ( $ 1, 2, 4, 8 $ ), ( $ 1, 3, 6 $ ), ( $ 1, 4, 8 $ ), ( $ 2, 4 $ ), ( $ 2, 6 $ ), ( $ 2, 8 $ ), ( $ 2, 4, 8 $ ), ( $ 3, 6 $ ), ( $ 4, 8 $ ).