C. Mixed Bits
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. Only the lowest $$$m$$$ bits of every integer are considered.

Let $$$a_l, a_{l+1}, \ldots, a_r$$$ be a non-empty subarray. A bit position $$$b$$$ ($$$0 \le b \lt m$$$) is called mixed in this subarray if there is at least one element whose $$$b$$$-th bit is $$$0$$$, and at least one element whose $$$b$$$-th bit is $$$1$$$.

The value of a subarray is the number of its mixed bit positions.

Count the subarrays whose value is exactly $$$k$$$.

Input

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 20$$$, $$$0 \le k \le m$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 2^m$$$).

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

Output

For each test case, print one integer — the number of subarrays whose value is exactly $$$k$$$.

Example
Input
5
3 3 1
0 1 3
4 2 0
1 1 3 3
3 3 2
0 1 3
4 3 3
0 7 0 7
5 4 1
5 5 7 7 5
Output
2
6
1
6
8
Note

In the first test case, the array is $$$[0,1,3]$$$. In binary, its elements are $$$000$$$, $$$001$$$, and $$$011$$$.

The subarrays $$$[0,1]$$$ and $$$[1,3]$$$ have exactly one mixed bit. No other subarray does.

In the fourth test case, every subarray of length at least two has all three bits mixed.