In the world of Deepwoken, there exists an ancient artifact — Tablet of Infinite Knowledge, on which a sequence of $$$n$$$ mysterious symbols (each symbol is an integer) is engraved.

It is said that the true power of the artifact can only be revealed by finding all sacred fragments — continuous segments of the tablet that contain exactly $$$k$$$ distinct numbers, and their length must be between $$$l$$$ and $$$r$$$ (inclusive).

Formally: Given a sequence $$$a$$$ of length $$$n$$$ and integers $$$k$$$, $$$l$$$, $$$r$$$. You need to find the number of such boundaries $$$b$$$ and $$$c$$$ such that:

$$$1 \le b \le c \le n$$$;
among the elements [$$$a_{b}, a_{b + 1}, \dots, a_{c}$$$] there are exactly $$$k$$$ distinct numbers;
$$$l \leq c - b + 1 \leq r$$$.

Input

Each test consists of several test cases.

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following describes the test cases.

The first line of each test case contains four integers: $$$n$$$, $$$k$$$, $$$l$$$, and $$$r$$$ $$$( 1 \le k \le n \le 2 \cdot 10^5, 1 \le l \le r \le n)$$$.

The second line contains $$$n$$$ numbers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the mysterious symbols.

It is guaranteed that the total value of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test, output a single integer on a separate line — the number of continuous subarrays that meet the specified conditions.

Note

In the first test case $$$a=[5]$$$, there is only one subarray $$$[5]$$$, which has a length of 1 and contains exactly $$$1$$$ distinct number.

In the fourth test case $$$a=[7,7,7,7]$$$, any subarray of identical numbers gives exactly $$$1$$$ distinct number. The start and end of possible subarrays are:

Length $$$1$$$: $$$[1,1]$$$, $$$[2,2]$$$, $$$[3,3]$$$, $$$[4,4]$$$.
Length $$$2$$$: $$$[1,2]$$$, $$$[2,3]$$$, $$$[3,4]$$$.

In total: $$$7$$$.

In the fifth test case $$$a=[1,2,1,2,3,2,1]$$$:

Length $$$2$$$: all subarrays have only $$$2$$$ distinct numbers.
Length $$$3$$$: $$$[3,5]$$$, $$$[5,7]$$$.
Length $$$4$$$: $$$[2,5]$$$, $$$[3,6]$$$, $$$[4,7]$$$.

In total: $$$5$$$.

Hidden Knowledge of the Ancients

Examples