#P1779C. Least Prefix Sum
Least Prefix Sum
Description
Baltic, a famous chess player who is also a mathematician, has an array , and he can perform the following operation several (possibly ) times:
- Choose some index ();
- multiply with , that is, set .
Baltic's favorite number is , and he wants to be the smallest of all non-empty prefix sums. More formally, for each it should hold that
Please note that multiple smallest prefix sums may exist and that it is only required that is one of them.
Help Baltic find the minimum number of operations required to make the least of all prefix sums. It can be shown that a valid sequence of operations always exists.
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case contains two integers and () — the size of Baltic's array and his favorite number.
The second line contains integers () — the array.
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, print a single integer — the minimum number of required operations.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.
The first line of each test case contains two integers and () — the size of Baltic's array and his favorite number.
The second line contains integers () — the array.
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, print a single integer — the minimum number of required operations.
Note
In the first example, we perform the operation . The array becomes and the prefix sums, , are equal to . Thus is the smallest of all prefix sums.
In the second example, we perform the operation . The array becomes with prefix sums equal to .
In the third and fourth examples, is already the smallest of the prefix sums — no operation needs to be performed.
In the fifth example, a valid sequence of operations is:
- ,
- ,
- .
The array becomes and its prefix sums are . Note that and are both the smallest of the prefix sums (and this is a valid solution).