Playlist Selection

You are given a collection of songs and you must choose a subset (playlist) such that the sum of their durations is exactly S. However, you can only choose songs whose duration is at least L.

More formally, given a list of n songs with durations a₁, a₂, …, aₙ, and two integers S and L, you need to count the number of non-empty subsets (playlists) such that every song in the playlist satisfies aᵢ ≥ L and (\sum aᵢ = S).

For example, if n=4, S=10, L=3 and the songs are [3, 4, 2, 6], then we first remove songs less than 3 (i.e. 2 is removed) and we are left with [3, 4, 6]. In this case, the only valid subset is [4, 6] whose sum is 10.

inputFormat

The input is read from standard input. The first line contains a single integer T, the number of test cases. Then T test cases follow. Each test case begins with a line containing three integers n, S, and L, where n is the number of songs, S is the target total duration, and L is the minimum allowed duration for a song. The following line then contains n integers which represent the durations of the songs.

outputFormat

For each test case, output a single line containing one integer — the number of valid playlists (subsets) where every selected song has a duration that is at least L and the sum of the durations equals S.## sample

6
4 10 3
3 4 2 6
3 8 3
5 5 5
4 15 5
1 2 3 4
5 10 2
2 3 5 7 10
4 7 2
1 2 7 4
3 9 4
1 2 3

1
0
0
3
1
0