404414: GYM101502 F Building Numbers
Description
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 ai (l ≤ i ≤ r) will be built with the minimum number of operations.
InputThe 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 ≤ 105), 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 a1, a2, ..., an (1 ≤ ai ≤ 1018), giving the array a.
Then q lines follow, each line contains two integers l and r (1 ≤ l ≤ r ≤ n), giving the queries.
OutputFor each query, print a single line containing its answer.
ExampleInput1Output
5 3
4 7 11 8 10
4 5
1 5
3 3
7Note
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.