B. Large Array and Segments
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There is an array $$$a$$$ consisting of $$$n$$$ positive integers, and a positive integer $$$k$$$. An array $$$b$$$ is created from array $$$a$$$ according to the following rules:

  • $$$b$$$ contains $$$n \cdot k$$$ numbers;
  • the first $$$n$$$ numbers of array $$$b$$$ are the same as the numbers of array $$$a$$$, that is, $$$b_{i} = a_{i}$$$ for $$$i \le n$$$;
  • for any $$$i \gt n$$$, it holds that $$$b_{i} = b_{i - n}$$$.

For example, if $$$a = [2, 3, 1, 4]$$$ and $$$k = 3$$$, then $$$b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4]$$$.

Given a number $$$x$$$, it is required to count the number of such positions $$$l$$$ ($$$1 \le l \le n \cdot k$$$), for which there exists a position $$$r \ge l$$$, such that the sum of the elements of array $$$b$$$ on the segment $$$[l, r]$$$ is at least $$$x$$$ (in other words, $$$b_{l} + b_{l+1} + \dots + b_{r} \ge x$$$).

Input

Each test consists of several test cases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 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$$$, $$$k$$$, $$$x$$$ ($$$1 \le n, k \le 10^{5}$$$; $$$1 \le x \le 10^{18}$$$).

The second line of each test case contains $$$n$$$ integers $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^{8}$$$).

Additional constraints on the input:

  • the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^{5}$$$;
  • the sum of $$$k$$$ across all test cases does not exceed $$$2 \cdot 10^{5}$$$.
Output

For each test case, output one integer — the number of suitable positions $$$l$$$ in the array $$$b$$$.

Example
Input
7
5 3 10
3 4 2 1 5
15 97623 1300111
105 95 108 111 118 101 95 118 97 108 111 114 97 110 116
1 100000 1234567891011
1
1 1 1
1
1 1 1
2
2 1 2
1 1
2 1 5
2 1
Output
12
1452188
0
1
1
1
0
Note

In the first test case, the array $$$b$$$ looks like this:

$$$$$$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5]$$$$$$

There are $$$12$$$ positions $$$l$$$ for which there exists a suitable position $$$r$$$. Here are some (not all) of them:

  • $$$l = 1$$$, for which there is a position $$$r = 6$$$, the sum over the segment $$$[1, 6]$$$ equals $$$18$$$;
  • $$$l = 2$$$, for which there is a position $$$r = 5$$$, the sum over the segment $$$[2, 5]$$$ equals $$$12$$$;
  • $$$l = 6$$$, for which there is a position $$$r = 9$$$, the sum over the segment $$$[6, 9]$$$ equals $$$10$$$.