B"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: 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 <= t <= 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 <= n, q <= 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 <= a_i <= 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 <= l <= r <= 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 ), "...