M. Make It Divisible
time limit per test
2 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 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 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.

Input

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$$$.

Output

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$$$.

Example
Input
3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000
Output
3 8
0 0
100 5050
Note

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.