题目描述

Given a sequence $a_1, a_2, \cdots, a_n$ of length $n$ containing positive integers, we say an interval $[l, r]$ ($1 \le l \le r \le n$) is a $\textit{divisible interval}$ if there exists an integer $d$ such that $l \le d \le r$ and for all $l \le i \le r$, $a_i$ is divisible by $a_d$. We say the whole sequence is a $\textit{divisible sequence}$ if for all $1 \le l \le r \le n$, $[l, r]$ is a divisible interval.

Given another sequence $b_1, b_2, \cdots, b_n$ of length $n$ and an integer $k$, find all integers $x$ such that $1 \le x \le k$ and the sequence $b_1 + x, b_2 + x, \cdots, b_n + x$ is a divisible sequence. As the number of such integers might be large, you just need to output the number and the sum of all such integers.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 500$) indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \times 10^4$, $1 \le k \le 10^9$).

The second line contains $n$ integers $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le 10^9$).

It's guaranteed that the sum of $n$ of all test cases does not exceed $5 \times 10^4$.

输出格式

For each test case output one line containing two integers separated by a space, where the first integer is the number of valid $x$, and the second integer is the sum of all valid $x$.

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

3 8
0 0
100 5050

提示

For the first sample test case, $x = 1$, $x = 2$ and $x = 5$ are valid.

For the third sample test case, all $1 \le x \le 100$ are valid.