404414: GYM101502 F Building Numbers

In this problem, you can build a new number starting from 1, by performing the following operations as much as you need:

• Add 1 to the current number.
• Add the current number to itself (i.e. multiply it by 2).

For example, you can build number 8 starting from 1 with three operations . Also, you can build number 10 starting from 1 with five operations .

You are given an array a consisting of n integers, and q queries. Each query consisting of two integers l and r, such that the answer of each query is the total number of operations you need to preform to build all the numbers in the range from l to r (inclusive) from array a, such that each number a_i (l ≤ i ≤ r) will be built with the minimum number of operations.

The first line contains an integer T (1 ≤ T ≤ 50), where T is the number of test cases.

The first line of each test case contains two integers n and q (1 ≤ n, q ≤ 10⁵), where n is the size of the given array, and q is the number of queries.

The second line of each test case contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹⁸), giving the array a.

Then q lines follow, each line contains two integers l and r (1 ≤ l ≤ r ≤ n), giving the queries.

For each query, print a single line containing its answer.

1
5 3
4 7 11 8 10
4 5
1 5
3 3

7
18
5

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

In the first query, you need 3 operations to build number 8, and 4 operations to build number 10. So, the total number of operations is 7.