This is the easy version of the problem. The only difference is that in this version k = 0.

There is an array a_1, a_2, …, a_n of n positive integers. You should divide it into a minimal number of continuous segments, such that in each segment there are no two numbers (on different positions), whose product is a perfect square.

Moreover, it is allowed to do at most k such operations before the division: choose a number in the array and change its value to any positive integer. But in this version k = 0, so it is not important.

What is the minimum number of continuous segments you should use if you will make changes optimally?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains two integers n, k (1 ≤ n ≤ 2 ⋅ 10^5, k = 0).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7).

It's guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case print a single integer — the answer to the problem.

Example

Input


3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1


Output


3
2
1

Note

In the first test case the division may be as follows:

  * [18, 6] 
  * [2, 4] 
  * [1] 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
# define ll  long long  int
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
# define mod 1000000007
# define con continue
# define ret return
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// unordered_map<long long, int, custom_hash> safe_map;
/*
   #include <ext/pb_ds/assoc_container.hpp> 
   #include <ext/pb_ds/tree_policy.hpp> 
   using namespace __gnu_pbds;   
   #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
   // find_by_order() - Returns an iterator to the k-th largest element (counting from zero)
   // order_of_key()  - The number of items in a set that are strictly smaller than our item
*/
void func()
{
   #ifndef ONLINE_JUDGE
   freopen("in.txt", "r", stdin);
   freopen("out.txt", "w", stdout);
   #endif
   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}   
ll k[10000002]={0};
bool visit_r[10000002]={0};
ll prev_r[10000002]={0};
      bool sieve[10000002]={0};
int32_t  main()
{
   func();
   ll t;
   t=1;
   cin>>t;  
      ll p=1e7;

   sieve[1]=1;

   for(ll i=1;i<=10000000;i++)
    k[i]=i;
   for(ll i=2;i<=p;i++)
   {
    if(sieve[i]==0)
    {
        // cout<<i<<endl;
    
    for(ll j=2*i;j<=p;j=j+i)
    {
      sieve[j]=1;
    //   cout<<sieve[5]<<endl;
    //   if(j==18 && i*i==9)
    //      cout<<"yes\n";
    }}
   }
  while(t--)
  {
      ll n,p;
      cin>>n>>p;
     ll pos[n+2];
      ll arr[n+2];
      for(ll i=1;i<=n;i++)
      {
        cin>>arr[i];
        ll y=arr[i];
        if(visit_r[arr[i]]==true || sieve[arr[i]]==0)
        {
            // cout<<y<<" "<<k[arr[i]]<<endl;
           pos[i]=k[arr[i]];
           continue;
        }
        for(ll j=2;j<=sqrt(y);j++)
        {
            if(y%j==0)
            {
                while(k[arr[i]]%(j*j)==0)
                    k[arr[i]]/=(j*j);
                // while(y%j==0)
                //     y/=j;
            }
        }
        // cout<<y<<" "<<k[arr[i]]<<endl;
        //  cout<<k[arr[i]]<<endl;
        pos[i]=k[arr[i]];
        visit_r[arr[i]]=true;
        // cout<<pos[i]<<" "<<k[arr[i]]<<" "<<i<<endl;
      }
      ll end=0,ans=1;
      for(ll i=1;i<=n;i++)
      {
          
        //   cout<<end<<endl;
        ll a=pos[i];
        if(prev_r[a]>end)
        {
            ans++;
            end=i-1;
        }
        // cout<<prev_r[a]<<endl;
        prev_r[a]=i;
      }
      for(ll i=1;i<=n;i++)
      {
        //   cout<<pos[i]<<" "<<k[arr[i]]<<" "<<i<<endl;
        prev_r[pos[i]]=0;
      }
      cout<<ans<<endl;
    // cout<<prev_r[10]<<endl;
    // //   for(ll i=1;i<=n;i++)
    // //   {
    // //     //  cout<<k[arr[i]]<<endl;
    // //     pos[k[arr[i]]].clear();
    // //   }
  }
}
