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$$$.

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$$$.

Large Array and Segments

Examples