整数 $n$ 的一个组合（composition）是指一组有序的整数，其和为 $n$。两个元素相同但顺序不同的组合被视为不同的组合（这与划分（partition）不同）。例如，前几个整数的所有组合如下：

1: $\{1\}$ 2: $\{1+1, 2\}$ 3: $\{1+1+1, 1+2, 2+1, 3\}$ 4: $\{1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1, 4\}$

注意 $1+2$ 和 $2+1$ 在 $3$ 的组合中被计为不同的组合。正如你可能猜到的，对于 $n$，共有 $2^{(n-1)}$ 种组合。

在本题中，我们对 $n$ 的组合中的元素设定了条件。如果一个组合中没有任何元素属于集合 $S$，则称该组合“避开”（miss）集合 $S$。例如，前几个整数中避开偶数集合的组合如下：

1: $\{1\}$ 2: $\{1+1\}$ 3: $\{1+1+1, 3\}$ 4: $\{1+1+1+1, 1+3, 3+1\}$

没有奇数可以拥有避开奇数集合的组合，且任何仅由偶数组成的偶数组合必然是 $n/2$ 的组合的 $2$ 倍。

对于本题，你需要编写一个程序来计算输入整数 $n$ 的组合中，避开算术序列 $\{m + i \cdot k \mid i = 0, 1, \dots\}$ 中所有元素的组合数量。

输入格式

输入的第一行包含一个十进制整数 $P$ ($1 \le P \le 10000$)，表示随后数据组的数量。每组数据应被独立且相同地处理。

每组数据由单行输入组成。它包含数据组编号 $K$，后跟三个空格分隔的整数 $n, m$ 和 $k$，其中 ($1 \le n \le 30$) 且 ($0 \le m < k < 30$)。

输出格式

对于每组数据，输出一行。该行包含数据组编号 $K$，后跟一个空格，再后跟避开指定序列的 $n$ 的组合数量。

样例

输入 1

3
1 10 0 2
2 15 1 4
3 28 3 7

输出 1

1 55
2 235
3 18848806