In this problem, you can build a new number starting from 1, by performing the following operations as much as you need:
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*.
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 ≤ 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.
For each query, print a single line containing its answer.
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.
## Input
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 ≤ 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.
## Output
For each query, print a single line containing its answer.
[samples]
## Note
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.
**Definitions**
Let $ f(x) $ denote the minimum number of operations required to build the positive integer $ x $ starting from 1, where each operation is either:
- Multiply by 2: $ x \mapsto 2x $,
- Add 1: $ x \mapsto x + 1 $.
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n, q \in \mathbb{Z} $ denote the array size and number of queries.
- Let $ A = (a_1, a_2, \dots, a_n) $ be an array of integers with $ 1 \le a_i \le 10^{18} $.
- Let $ Q = \{(l_j, r_j) \mid j \in \{1, \dots, q\}\} $ be the set of queries, where $ 1 \le l_j \le r_j \le n $.
**Constraints**
1. $ 1 \le T \le 50 $
2. For each test case:
- $ 1 \le n, q \le 10^5 $
- $ 1 \le a_i \le 10^{18} $ for all $ i \in \{1, \dots, n\} $
- $ 1 \le l_j \le r_j \le n $ for all $ j \in \{1, \dots, q\} $
**Objective**
For each query $ (l_j, r_j) $, compute:
$$
\sum_{i = l_j}^{r_j} f(a_i)
$$