B. Large Array and Segmentstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThere 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 > 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$$$).InputEach 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}$$$. OutputFor each test case, output one integer — the number of suitable positions $$$l$$$ in the array $$$b$$$.ExampleInput75 3 103 4 2 1 515 97623 1300111105 95 108 111 118 101 95 118 97 108 111 114 97 110 1161 100000 123456789101111 1 111 1 122 1 21 12 1 52 1Output12
1452188
0
1
1
1
0
NoteIn 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$$$.