在圣安东尼奥，沿着河边（被称为 River Walk）在公园里享用玛格丽特酒是当地最受欢迎的活动之一。沿着 River Walk，从高档酒店到 Joe 的塔可和玛格丽特摊位，许多商家都有售卖玛格丽特酒。（本题不探讨 Joe 是如何获得酒牌的，这涉及德克萨斯州的政治，对于 ACM 竞赛题目来说太难了。）玛格丽特酒的价格取决于配料的数量和质量以及商家的环境。你已经分配了一定金额的钱用于品尝不同的玛格丽特酒。

给定每个商家售卖单杯玛格丽特酒的价格（包含适用的税费和小费）以及你分配的预算，请找出你可以购买多少种不同的“极大”组合。每个商家最多只能选择一杯玛格丽特酒。一个有效的组合必须满足：总价格不超过分配的预算，且剩余金额（分配金额 - 总价格）必须小于任何未被选择的商家的玛格丽特酒价格。（否则，你本可以将该商家加入到组合中。）

例如，假设你有 $25$ 美元可供消费，各商家的价格（以美元为单位的整数）如下：

那么可能的组合（及其价格）为： ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ(20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) 和 HJ(21)。

因此，组合的总数为 15。

输入格式

输入的第一行包含一个整数，指定后续的数据集数量 $N$ ($1 \le N \le 1000$)。每个数据集的第一行包含两个整数 $V$ 和 $D$，分别代表商家数量 ($1 \le V \le 30$) 和可供消费的美元金额 ($1 \le D \le 1000$)。这两个值由一个或多个空格分隔。每个数据集的其余部分包含一行或多行，每行包含一个或多个整数，代表每个商家的玛格丽特酒价格。总共会指定 $V$ 个价格值。玛格丽特酒的价格至少为 1。输入值将确保结果适合 32 位无符号整数。

输出格式

对于每个问题实例，输出应为单行，包含数据集编号，后跟一个空格，然后是该问题实例的组合数量。

说明

某些针对此问题的解决方法在商家数量较多时可能是指数级的。对于这些方法，在商家数量较多的问题实例（如第二个样例）中，可能会超出时间限制。

样例

输入 1

2 
6 25 
8 9 8 7 16 5 
30 250 
1 2 3 4 5 6 7 8 9 10 11 
12 13 14 15 16 17 18 19 20 
21 22 23 24 25 26 27 28 29 30

输出 1

1 15 
2 16509438