A sequence is called M-sequence if after removing zero or more elements from the sequence the GCD of its remaining elements is M. The M-value is the summation of the removed elements. The significant point is if there are multiple ways of element removing to make the sequence M-sequence, we have to remove such way so that M-value is minimum possible.
Let’s consider the following sequence:
3-value = 6 ```
Here 9, 2, 4, 6 is a 3-sequence because if we remove 2, 4 the GCD of remaining elements 9, 6 will be 3 and summation of removed elements (2,4) will be M-value = 6.
Now, if you are given a sequence, find the continuous subsequence whose M-value is minimum possible. For example, consider the following sequence when M = 5,
```4, 15, 2, 10, 8```
Here, continuous subsequence 15, 2, 10 of the above sequence is a 5-sequence where 5-value is 2. No other continuous sequence is available in this sequence which gives 5-sequence.
Input
In the first line, there will be an integer T (1 ≤ T ≤ 10), the number of test cases. It will be followed by T test cases.
First line of each test case will contain two integer N, M where N is the number of elements in the input sequence and M is described above.
The next line will contain N elements A1, A2,..., An of the input sequence.
0 <= N, <= 105
0 <= M, Ai <= 10 13
Output
Find the continuous subsequence whose M-value is minimum possible. Print that minimum M-value, taken modulo 109+7. If there is no M-sequence, print 0.
Sample
| Input | Output |
|---|---|
1 10 5 4 15 2 4 10 8 25 2 20 4 | 2 |
