虽然最近学校不检查听课情况了，浪哥还是很烦恼，因为他遇到了一个问题：
一张图里有 $n$ 个点，第 $i$ 个点与第 $(i + 1)$ 个点之间连有一条长度为 $d_i$ 的双向边 $(i = 1, 2, \cdots, n - 1)$，每条双向边可以走任意多次，除此之外没有其他边可以走。
考虑从第 $1$ 个点走到第 $n$ 个点且路径长度不超过 $m$ 的所有路径，问这些路径中路径长度有多少种可能的不同取值。
你能帮他排忧解难吗？
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行包含两个整数 $n$ 和 $m$，含义见题目描述。
第二行包含 $(n - 1)$ 个整数表示 $d_1, d_2, \cdots, d_{n - 1}$。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
保证所有的数据满足 $1 \leq T \leq 200,$ $1 \leq n \leq 2000,$ $1 \leq m \leq 10^6,$ $\sum{m} \leq 2 \times 10^7,$ $1 \leq d_i \leq 10^9$。
对于每组数据，输出一行，包含一个整数，表示可能的路径长度数量。
1
3 10
2 32对于第一组数据，存在一条长度为 $5$ 的路径 $1 \to 2 \to 3$，一条长度为 $9$ 的路径 $1 \to 2 \to 1 \to 2 \to 3$，其他路径长度均超过 $10$。