diagram 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.
Consider an undirected weighted diagram 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:
Assuming gcd(
Assuming i+1=j, there is an edge of weight p among I and j.
Here gcd(x,y,… ) signifies the best normal divisor (GCD) of integers x, y, ....
Note that there could be numerous edges among I and j if both of the above conditions are valid, and assuming both the conditions come up short for I and j, there is no edge between these vertices.
The objective is to find the heaviness of the base traversing tree of this chart.
Input
The principal line contains a solitary integer t (1≤t≤104) — the number of experiments.
The primary 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 relating chart
Step by step
Solved in 3 steps with 1 images
