Есть массив `a`, состоящий из `n` целых положительных чисел, и целое положительное число `k`. Из массива `a` создается массив `b` по следующим правилам: - массив `b` содержит `n*k` чисел; - первые `n` чисел массива `b` совпадают с числами массива `a`, то

Есть массив a, состоящий из n целых положительных чисел и целое положительное число k. Из массива a создается массив b

по следующим правилам:

массив b

содержит n⋅k
чисел;
первые n
чисел массива b совпадают с числами массива a, то есть bi=ai для i≤n
;
для любого i>n
выполняется bi=bi−n

.

Например, если a=[2,3,1,4]
и k=3, то b=[2,3,1,4,2,3,1,4,2,3,1,4]

.

Дано число x
. Необходимо посчитать количество таких позиций l (1≤l≤n⋅k), для которых найдется такая позиция r≥l, что сумма элементов массива b на отрезке [l,r] составит не менее x (то есть bl+bl+1+⋯+br≥x

).
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤104

) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа n
, k, x (1≤n,k≤105; 1≤x≤1018

).

Вторая строка каждого набора входных данных содержит n
целых положительных чисел ai (1≤ai≤108

).

Дополнительные ограничения на входные данные:

сумма n

по всем наборам входных данных не превышает 2⋅105
;
сумма k
по всем наборам входных данных не превышает 2⋅105

.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество подходящих позиций l
в массиве b

.
Пример
Входные данные
Скопировать

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

Примечание

В первом наборе входных данных массив 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.