Let a given sequence S (of length n) of positive integers be called x-medial (where x is a positive integer) if:

1. n is odd, and the median of the sequence (the ((n+1)/2)^th largest term) equals x. OR
2. n is even, and both the central terms ( (n/2)^th largest and (n/2+1)^th largest) are equal to x.

Given a sequence A (of length N) of positive integers and an integer k, find out how many of its sub-sequences are k-medial.

A sub-sequence of A is any sequence {A[i], A[i+1], A[i+2]... , A[j]}, where 0 ≤ i ≤ j < N.

Input

The first line contains T (T≤15), the number of test cases.

Each test case consists of 2 lines. The first line contains the numbers N (1≤N≤10⁵) and k (1≤k≤10⁹), seperated by a single space.

The next line contains the sequence A (N terms, each ≤ 10⁹,  seperated by single spaces between them).

Output

Output T lines, each containing a single integer, equal to the number of k-medial sub-sequences.

Example

Input:
2

3 5

17 5 2

5 2

1 2 2 3 7

Output:
2

7