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]$$</p><p>There are$12$positions$l$for which there exists a suitable position$r$. Here are some (not all) of them:</p><ul> <li>$l = 1$, for which there is a position$r = 6$, the sum over the segment$[1, 6]$equals$18$; </li><li>$l = 2$, for which there is a position$r = 5$, the sum over the segment$[2, 5]$equals$12$; </li><li>$l = 6$, for which there is a position$r = 9$, the sum over the segment$[6, 9]$equals$10$. ## Samples ```input1 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 ``` ```output1 12 1452188 0 1 1 1 0 ```$$