Untitled

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for(int i=0;i<n;i++){

        int m;
        cin >> m;
        int arr[m];

        for(int i=0;i<m;i++){
            cin >> arr[i];
        }

        int arr1[m];

        for(int i=0;i<m;i++){

            if(i==(m-1)){
                arr1[m-1] = __gcd(arr[m-1],arr[0]);
            }
            else{

                arr1[i] = __gcd(arr[i],arr[i+1]);
            }

        }

        for(int i=0;i<m;i++){
            cout << arr1[i] << " ";
        }
        cout << endl;

        unordered_map<int, int> hash1;
        for (int i=0; i<m; i++)
        {
            hash1[arr[i]]++;
        }
        int maxCount1 = 0;

        for (auto i : hash1)
        {
            if (maxCount1 < i.second)
            {
                maxCount1 = i.second;
            }
        }


        unordered_map<int, int> hash2;
        for (int i=0; i<m; i++)
        {
            hash2[arr1[i]]++;
        }
        int maxCount2 = 0;

        for (auto i : hash2)
        {
            if (maxCount2 < i.second)
            {
                maxCount2 = i.second;
            }
        }

        cout << m-maxCount1 << " " << m-maxCount2+1 << endl;


        if((m-maxCount1)==0){
            cout << 0 << endl;
        }
        else{
            cout << min((m-maxCount2+1),(m-maxCount1)) << endl;
        }

    }

    return 0;
}