given an exhibit an of n (n≥2) positive integers and an integer p. Consider an undirected weighted chart of n vertices numbered from 1 to n for which the edges between the vertices I and j (i
Correct answer will be upvoted else downvoted. Computer science.
You are given an exhibit an of n (n≥2) positive integers and an integer p. Consider an undirected weighted chart of n vertices numbered from 1 to n for which the edges between the vertices I and j (i<j) are included the accompanying way:
In the event that gcd(
On the off chance that i+1=j, there is an edge of weight p among I and j.
Here gcd(x,y,… ) means the best normal divisor (GCD) of integers x, y, ....
Note that there could be different edges among I and j if both of the above conditions are valid, and assuming both the conditions fall flat for I and j, there is no edge between these vertices.
The objective is to find the heaviness of the base crossing tree of this chart.
Input
The main line contains a solitary integer t (1≤t≤104) — the number of experiments.
The principal line of each experiment contains two integers n (2≤n≤2⋅105) and p (1≤p≤109) — the number of hubs and the boundary p.
The subsequent line contains n integers a1,a2,a3,… ,an (1≤ai≤109).
It is ensured that the amount of n over all experiments doesn't surpass 2⋅105.
Output
Output t lines. For each experiment print the heaviness of the comparing diagram
Step by step
Solved in 3 steps with 1 images
