该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小美和小丁在玩智力游戏，游戏规则是这样的：小美会给出一个正整数t和一个长度为n的数组A。然后让计算机根据下面的方法，生成了一个数组B：

• 数组B的长度为n * t;
• 对于i ≤ n，有 $B_i = A_i$;
• 对于i > n，有$B_i = B_{i-n}$。

例如：若A = [5, 1, 7]且t = 4，则B = [5, 1, 7, 5, 1, 7, 5, 1, 7, 5, 1, 7]。

现在，小美又给出一个数p，小丁需要找出，在数组B中满足下面条件的位置L的数量：

• L满足1 ≤ L ≤ n * t
• 存在某个位置R ≥ L，使得数组B在区间[L, R]上的元素之和至少为p（即$B_L + B_{L+1} + ... + B_R ≥ p$）。

输入描述

多组数据。 第一行为一个整数k。 接下来有k组数据，对于每组数据：

• 第一行：三个整数n, t, p
• 第二行：n个数，A1, A2, ..., An

输出描述

对于每组数据，输出一行，一个整数，表示数组B中满足条件的位置L的数量。

样例输入

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

样例输出

12
1452188
0
1
1
1
0

数据范围

• 40%的数据：k = 1
• 70%的数据：k ≤ 100
• 35%的数据：t = 1
• 对于100%的数据：
  • $1 < k < 10^4$
  • $1 < n, t < 2 \times 10^5$
  • $1 < p < 10^{18}$
  • $1 < a_i < 10^8$
  • 对于每个测试点，n之和不超过$2 \times 10^6$，t之和不超过$2 \times 10^6$

样例解释

对于第一组数据： 5 3 10 3 4 2 1 5 t = 3，那么B数组为3,4,2,1,5,3,4,2,1,5,3,4,2,1,5。下标L从1到12，都可以找到一个下标R，满足[L, R]之间的元素和不小于10。