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⁹), separated by a single space.

The next line contains the sequence A (N terms, each ≤ 10⁹, separated 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