有一个数组 $$$a$$$ 由 $$$n$$$ 组成 积极 整数,以及正整数 $$$k$$$。根据以下规则从数组 $$$a$$$ 创建数组 $$$b$$$:
- $$$b$$$ 包含 $$$n \cdot k$$$ 数字;
- 数组$$$b$$$的前$$$n$$$个数与数组$$$a$$$的个数相同,即$$$b_{i} = a_{i}$$$ for $$$i \le n$$$;
- 对于任何$$$i \gt 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$$$,使得 $$$[l, r]$$$ 段上数组 $$$b$$$ 的元素之和为 至少 $$$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$$$ 的数量。
示例
输入复制
75 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 1
输出复制
12 1452188 0 1 1 1 0
注意
在第一个测试用例中,数组 $$$b$$$ 如下所示:
$$$$$$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5]$$$$$$
有 $$$12$$$ 头寸 $$$l$$$,其中存在合适的头寸 $$$r$$$。以下是其中一些(不是全部):
- $$$l = 1$$$,其中有一个位置 $$$r = 6$$$,段 $$$[1, 6]$$$ 上的总和等于 $$$18$$$;
- $$$l = 2$$$,其中有一个位置 $$$r = 5$$$,段 $$$[2, 5]$$$ 的总和等于 $$$12$$$;
- $$$l = 6$$$,其中有一个位置 $$$r = 9$$$,段 $$$[6, 9]$$$ 上的总和等于 $$$10$$$。