M. Banana Monitor
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a Software Development Engineer at Banana Corp. Among many software in Banana Corp, you work for Banana Video. Banana video is a website where Banana customers can stream series, movies and sports.

You log the number of Banana customers (traffic) that reaches your website each minute. You have configured your website to support a fixed number of customers at a time. Now you want to monitor the traffic in the website and get alarmed if the traffic exceeds the expected threshold for a continuous period.

You have written a function $$$bananaMonitor(X_i, X_{max}, A, C)$$$ that is called at the end of each minute which takes four parameters:

  • $$$X_i$$$ : CURRENT_TRAFFIC. This variable is the traffic at $$$i$$$-th minute
  • $$$X_{max}$$$ : MAX_TRAFFIC. The maximum expected traffic at any minute in the webpage
  • $$$A$$$ - ALARM_AFTER. If the number of traffic exceeds $$$X_{max}$$$ for $$$A$$$ consecutive minutes, then set the alarm and put the monitor in alarmed state.
  • $$$C$$$ - CLEAR_AFTER. If the monitor is at alarm, and the traffic is less than or equal $$$X_{max}$$$ for $$$C$$$ consecutive minutes, then clear the alarm and set the monitor in normal state.

Once the monitor is in alarm, it will continue to be in alarm untill it is cleared. If the monitor is in normal state it continues to be so until alarm is set. It is assured that the monitor will be at normal state in the beginning of each test case.

Now you are given $$$X_i$$$ for $$$N$$$ consecutive minutes. Could you tell the total count of minutes for which the monitor was in alarmed state?

Input

First line of each input will contain an integer $$$T$$$ which is the number of input in each test cases.

There will be $$$4$$$ integers in the first line of each test case $$$N$$$, $$$X_{max}$$$, $$$A$$$, $$$C$$$. Next line will contain $$$N$$$ integers $$$X_1$$$ $$$X_2$$$ $$$X_3$$$ ... $$$X_N$$$, the traffic in each minute.

$$$1 \leq T \leq 100$$$

$$$1 \leq N, A, C \leq 100000$$$

$$$0 \leq X_{max}, X_i \leq 100000$$$

Output

Output an integer $$$M$$$ for each test case, Where $$$M$$$ will be total count of minutes for which the monitor was in alarmed state.

Example
Input
2
9 5 3 2
2 6 8 9 6 5 4 3 6
4 1 1 1
1 2 0 2
Output
3
2