Practice on Toph

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

M-Sequence

By mahbubcseju · Limits 2s, 512 MB

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.

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

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


Discussion
Statistics

64% Solution Ratio

aniks2645Earliest, 1M ago

YouKnowWhoFastest, 0.1s

YouKnowWhoLightest, 918 kB

YouKnowWhoShortest, 1523B

Submit

Login to submit