给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$，如果存在一个整数 $d$ 满足 $l \le d \le r$，且对于所有 $l \le i \le r$，$a_i$ 都能被 $a_d$ 整除，则称区间 $[l, r]$ ($1 \le l \le r \le n$) 为可整除区间。如果对于所有 $1 \le l \le r \le n$，区间 $[l, r]$ 都是可整除区间，则称整个序列为可整除序列。

给定另一个长度为 $n$ 的序列 $b_1, b_2, \dots, b_n$ 和一个整数 $k$，求所有满足 $1 \le x \le k$ 且序列 $b_1 + x, b_2 + x, \dots, b_n + x$ 为可整除序列的整数 $x$。由于满足条件的整数可能很多，你只需要输出满足条件的 $x$ 的个数以及所有这些 $x$ 的和。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 500$)，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 5 \times 10^4, 1 \le k \le 10^9$)。

第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$)。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^4$。

输出格式

对于每组测试数据，输出一行，包含两个由空格分隔的整数，第一个整数是满足条件的 $x$ 的个数，第二个整数是所有满足条件的 $x$ 的和。

样例

样例输入 1

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

样例输出 1

3 8
0 0
100 5050

说明

对于第一组样例，满足条件的 $x$ 为 $x = 1, x = 2$ 和 $x = 5$。

对于第三组样例，所有 $1 \le x \le 100$ 均满足条件。