Thief of the Circular Village

Time limit1sMemory limit256 MB

Summary

Count the starting positions of a circular window of M houses whose total amount stays below K.

Level: Easy3 of 10
Topics: Sliding window, Prefix sum, Array, Implementation
Solved: No attempts yet

Problem

A village has N houses standing next to one another in order. The first house and the last house are neighbors too, so the houses form one circle.

The picture shows a village with N = 8. The house holding 3 is next to the house holding 9 and the house holding 4, and the house holding 5 is next to the house holding 6 and the house holding 7. Everyone in the village keeps money at home, and the number written on a house is the amount kept there.

One day a thief comes to the village. To steal quickly and run, the thief picks M houses that are next to one another and takes all the money kept in those M houses. With M = 3 the thief can take 14 from the houses holding 3, 4 and 7 and then run, or take 15 from the houses holding 5, 6 and 4 and then run.

If the stolen money adds up to K or more, an automatic alarm goes off and the thief is caught on the spot. With M = 3 and K = 15, the houses holding 3, 4 and 7 give 14 and the thief gets away, while the houses holding 5, 6 and 4 give 15 and the alarm catches the thief.

You are given the number of houses N, the number M of consecutive houses the thief robs, the smallest amount K that triggers the alarm, and the money kept in each house. Write a program that counts the choices that let the thief get away. A choice is identified by the house where the theft starts, so there are N candidates, and when M = N two different starting houses still count as two different choices.

Input

Input comes from standard input. The first line has the number of test cases T.

The first line of each test case has the number of houses in the village N ( $1 \le N \le 100{,}000$ ), the number of consecutive houses the thief robs M ( $1 \le M \le N$ ), and the smallest amount K that triggers the automatic alarm ( $1 \le K \le 1{,}000{,}000{,}000$ , K is an integer), separated by spaces.

The second line has the money kept in the N houses in clockwise order, separated by spaces. The houses matching the first value and the last value of that line are neighbors as well. The money kept in a house is an integer between 1 and 10,000.

Output

Output goes to standard output. For each test case, print on its own line the number of choices of M consecutive houses that let the thief steal without triggering the automatic alarm.

Examples4

Example 1
Input
```
2
8 3 15
3 4 7 5 6 4 2 9
2 1 5
4 5
```
Expected output
```
3
1
```
Example 2
Input
```
3
1 1 1
1
1 1 2
1
1 1 10000
10000
```
Expected output
```
0
1
0
```

Example 3

Input

Expected output

5
0

Example 4
Input
```
1
6 2 1
1 1 1 1 1 1
```
Expected output
```
0
```