Iris has just learned multiplication in her Maths lessons. However, since her brain is unable to withstand too complex calculations, she could not multiply two integers with the product greater than (k) together. Otherwise, her brain may explode! Her teacher sets a difficult task every day as her daily summer holiday homework. Now she is given an array (a) consisting of (n) elements, and she needs to calculate the product of each two adjacent elements (that is, (a_1 \cdot a_2), (a_2 \cdot a_3), and so on). Iris wants her brain to work safely, and in order to do that, she would like to modify the array (a) in such a way that (a_i \cdot a_{i + 1} \leq k) holds for every (1 \leq i < n). There are two types of operations she can perform: She can rearrange the elements of the array (a) in an arbitrary way. She can select an arbitrary element of the array (a) and change its value to an arbitrary integer from (1) to (k). Iris wants to minimize the number of operations of type (2) that she uses. However, that's completely not the end of the summer holiday! Summer holiday lasts for (q) days, and on the (i)-th day, Iris is asked to solve the Math homework for the subarray (b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}). Help Iris and tell her the minimum number of type (2) operations she needs to perform for each day. Note that the operations are independent for each day, i.e. the array (b) is not changed. Each test consists of multiple test cases. The first line contains a single integer (t) ((1 \leq t \leq 5\cdot 10^4)) — the number of test cases. The description of the test cases follows. The first line of each test case contains three integers (n), (q) and (k) ((2 \leq n \leq 10^5), (1 \leq q \leq 10^5), (1 \leq k \leq 10^6)) — the length of array (b), the number of days, and the upper bound for the multiplication calculation. The second line of each test case con