The boy Smilo is learning algorithms with a teacher named Brukhovich.
Over the course of the year, Brukhovich will administerexams. For each exam, its difficulty is known, which is a non-negative integer.
Smilo doesn’t like when the greatest common divisor of the difficulties of two consecutive exams is equal to sadness of the academic year to be the number of such pairs of exams. More formally, the sadness is the number of indices ( ) such that , where is the greatest common divisor of integers and .. Therefore, he considers the
Brukhovich wants to minimize the sadness of the year of Smilo. To do this, he can set the difficulty of any exam to. However, Brukhovich doesn’t want to make his students’ lives too easy. Therefore, he will perform this action no more than times.
Help Smilo determine the minimum sadness that Brukhovich can achieve if he performs no more thanoperations.
As a reminder, the greatest common divisor (GCD) of two non-negative integersand is the maximum integer that is a divisor of both and and is denoted as . In particular, for any non-negative integer .
The first line contains a single integer( ) — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains two integersand ( ) — the total number of exams and the maximum number of exams that can be simplified, respectively.
The second line of each test case containsintegers — the elements of array , which are the difficulties of the exams ( ).
It is guaranteed that the sum ofacross all test cases does not exceed .
For each test case, output the minimum possible sadness that can be achieved by performing no more thanoperations.
1 0 2 2 0 5 5 2 1
In the first test case, a sadness ofcan be achieved. To this, you can simplify the second and fourth exams. After this, there will be only one pair of adjacent exams with a greatest common divisor (GCD) equal to one, which is the first and second exams.
In the second test case, a sadness ofcan be achieved by simplifying the second and fourth exams.