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] 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e7+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
int prm[N],mind[N],cnt;
bool vis[N];
void init(int n){
	for(int i = 2 ; i <= n ; ++i ){
		if(!vis[i]){
			prm[cnt++] = i;
			mind[i] = i;
		}
		for(int j = 0 ; prm[j] <= n / i ; ++j){
			vis[prm[j] * i] = true;
			mind[prm[j] * i] = prm[j];
			if(i % prm[j] == 0) break;
		}
	}
}
int a[N / 100 + 10];
void solve(){
	cin >> n >> k;
	for(int i = 1 ; i <= n ; ++i ) a[i] = 1;
	for(int i = 1 ; i <= n ; ++i ){
		int x;
		cin >> x;
		while(x > 1){
			int p = mind[x];
			int cnt = 0;
			while(x % p == 0) x /= p,cnt++;
			if(cnt % 2) a[i] *= p;
		}
	}
	int ans = 1,l = 0;
	map<int,int> mp;
	for(int i = 1 ; i <= n ; ++i ){
		if(mp.count(a[i]) && mp[a[i]] >= l){
			ans++;
			l = i;
		}
		mp[a[i]] = i;
	}
	cout << ans << endl;
}
signed main(){
	IOS;
	init(N - 1); 
	int tt;
	cin >> tt;
	while(tt--) 
	solve();
	return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/
