Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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:

```
9, 2, 4, 6
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.

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 A_{1}, A_{2},…, A_{n} of the input sequence.

0 <= N, <= 10^{5}

0 <= M, A_{i} <= 10 ^{13}

Find the continuous subsequence whose M-value is minimum possible. Print that minimum M-value, taken modulo 10^{9}+7. If there is no M-sequence, print 0.

Input | Output |
---|---|

1 10 5 4 15 2 4 10 8 25 2 20 4 | 2 |

64% Solution Ratio

aniks2645Earliest,

YouKnowWhoFastest, 0.1s

YouKnowWhoLightest, 918 kB

YouKnowWhoShortest, 1523B

Login to submit