You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 512.0 MB

Description

You are playing a game in an array \(A\) of size \(N\). In this game your character thakur starts in the \(1st\) position of the array and wants to go to the \(Nth\) position.

thakur only has two types of moves :
if his current position is \(i\)

• He can go to \(i+1\)th position. it will cost him \(K\) coins.
• He can go to any position \(j>i\) . it will cost him \(Ai / GCD(Ai,Aj)\)

You have the array \(A\) and the constant \(K\). What is the minimum cost to reach position \(N\).

Input

First line takes an integer \(T\) : number of testcases
First line of each testcase takes two integer \(N,K\) : size of the array and the constant value.
Second line of each testcase takes \(N\) integers \(A1,A2,A3.....An\)

\(1 <= T <= 100\)
\(1 <= N <= 2*10^5\)
\(1 <= K <= 100\)
\(1 <= Ai <= 2*10^5\)

sum of \(N\) over all testcase will not exceed \(2*10^5\)

Output

one integer in each of \(T\) lines : minimum cost to go to position \(N\).

Sample

3
3 5
6 3 2
3 1
6 3 2
3 5
6 3 1

3
2
5

in the first testcase:
Thakur can go to position 1 to N by the 2nd type of operation. the cost is 6 / GCD(6,2) = 3

in the second testcase:
Thakur can go to position 1 to 2 by the first operation it will cost him 1 coin.
then again he can use the first operation to go to 3rd position from 2.
so the total cost is 1 + 1 = 2