题目描述

给定一个由 $n$ 个正整数组成的数组 $a$，以及一个正整数 $k$。根据以下规则从数组 $a$ 创建数组 $b$：

• 数组 $b$ 包含 $n \cdot k$ 个元素；
• 数组 $b$ 的前 $n$ 个元素与数组 $a$ 相同，即对于 $i \le n$，有 $b_{i} = a_{i}$；
• 对于任意 $i > n$，有 $b_{i} = b_{i - n}$。

例如，若 $a = [2, 3, 1, 4]$ 且 $k = 3$，则 $b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4]$。

给定一个数 $x$，要求统计满足以下条件的位置 $l$（$1 \le l \le n \cdot k$）的数量：存在位置 $r \ge l$，使得数组 $b$ 在区间 $[l, r]$ 上的元素之和不小于 $x$（即 $b_{l} + b_{l+1} + \dots + b_{r} \ge x$）。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^{4}$）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$k$、$x$（$1 \le n, k \le 10^{5}$；$1 \le x \le 10^{18}$）。

第二行包含 $n$ 个整数 $a_{i}$（$1 \le a_{i} \le 10^{8}$）。

输入数据的额外限制：

• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^{5}$；
• 所有测试用例的 $k$ 之和不超过 $2 \cdot 10^{5}$。

输出格式

对于每个测试用例，输出一个整数——数组 $b$ 中满足条件的位置 $l$ 的数量。

输入输出样例 #1

输入 #1

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

输出 #1

12
1452188
0
1
1
1
0

说明/提示

在第一个测试用例中，数组 $b$ 如下所示：

共有 $12$ 个位置 $l$ 满足存在对应的位置 $r$。以下是其中部分（非全部）示例：

• $l = 1$，存在 $r = 6$，区间 $[1, 6]$ 的和为 $18$；
• $l = 2$，存在 $r = 5$，区间 $[2, 5]$ 的和为 $12$；
• $l = 6$，存在 $r = 9$，区间 $[6, 9]$ 的和为 $10$。