题目描述

有N件物品和一个体积是$\red C$的背包。

需要把一些物品装到背包里使得剩下的物品无法再放入，求方案数。

每件物品有一个体积$\red {V_i}$。

输入格式

本题包含多组测试数据。

第一行输入一个整数，表示数据组数。

接下来对于每组数据的第一行是两个整数，$\red N$，$\red C$。

然后$\red N$个整数$\red {V_i}$，表示每个物品的体积。

输出格式

对于每个测试数据，输出$\red 2$个整数，第一个表示数据编号，第二个是题目要求的方案数。

样例

输入样例

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 15
2 16509438

提示

$\red {40\%}$数据组数小于等于$\red {20}$。

$\red {100\%}$数据组数小于等于$\red {1000}$。

$\red {1<=C<=1000,1<=N<=30}$。