{"problem":{"name":"F. Building Numbers","description":{"content":"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 . A","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10150F"},"statements":[{"statement_type":"Markdown","content":"In this problem, you can build a new number starting from 1, by performing the following operations as much as you need: \n\nFor example, you can build number 8 starting from 1 with three operations . Also, you can build number 10 starting from 1 with five operations .\n\nYou 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*.\n\nThe first line contains an integer T (1 ≤ T ≤ 50), where T is the number of test cases.\n\nThe 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.\n\nThe second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1018), giving the array a.\n\nThen q lines follow, each line contains two integers l and r (1 ≤ l ≤ r ≤ n), giving the queries.\n\nFor each query, print a single line containing its answer.\n\nAs 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.\n\nIn 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. \n\n## Input\n\nThe 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.\n\n## Output\n\nFor each query, print a single line containing its answer.\n\n[samples]\n\n## Note\n\nAs 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ f(x) $ denote the minimum number of operations required to build the positive integer $ x $ starting from 1, where each operation is either:  \n- Multiply by 2: $ x \\mapsto 2x $,  \n- Add 1: $ x \\mapsto x + 1 $.  \n\nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, q \\in \\mathbb{Z} $ denote the array size and number of queries.  \n- Let $ A = (a_1, a_2, \\dots, a_n) $ be an array of integers with $ 1 \\le a_i \\le 10^{18} $.  \n- 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 $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. For each test case:  \n   - $ 1 \\le n, q \\le 10^5 $  \n   - $ 1 \\le a_i \\le 10^{18} $ for all $ i \\in \\{1, \\dots, n\\} $  \n   - $ 1 \\le l_j \\le r_j \\le n $ for all $ j \\in \\{1, \\dots, q\\} $  \n\n**Objective**  \nFor each query $ (l_j, r_j) $, compute:  \n$$\n\\sum_{i = l_j}^{r_j} f(a_i)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10150F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}