题目描述

给定一个长为 $n$ 的数组 $a$，从中选出若干个在 $[l,r]$ 区间的数，使得总和不大于 $k$。求最多个数。

输入格式

第一行一个 $t$，表示数据组数。

每一组数据中：

第一行有四个整数 $n$ , $l$ , $r$ , $k$ ( $1 \le n \le 100$ , $1 \le l \le r \le 10^9$ , $1 \le k \le 10^9$ )。

第二行有 $n$ 个整数，表示数组 $a$。

输出格式

对于每一组数据输出一行一个整数，表示最大个数。

样例

8
3 1 100 100
50 100 50
6 3 5 10
1 2 3 4 5 6
6 3 5 21
1 2 3 4 5 6
10 50 69 100
20 30 40 77 1 1 12 4 70 10000
3 50 80 30
20 60 70
10 2 7 100
2 2 2 2 2 7 7 7 7 7
4 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 1 1 1
1

2
2
3
0
0
10
1
1