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] 
#===========Template===============
from io import BytesIO, IOBase
import sys,os
inpl=lambda:list(map(int,input().split()))
inpm=lambda:map(int,input().split())
inpi=lambda:int(input())
inp=lambda:input()
rev,ra,l=reversed,range,len
P=print
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")

#=========I/p O/p ========================================#
from bisect import bisect_left as bl 
from bisect import bisect_right as br
import sys,operator,math,operator
from collections import Counter 


#==============To chaliye shuru krte he ====================#
ar=[]
def p_s(n): 
    prime = [True for i in range(n + 1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, n + 1, p): 
                prime[i] = False
        p += 1
    prime[0]= False
    prime[1]= False
    for i in ra(n+1):
        if prime[i]:
            ar.append(i)
pre=[0]*((10**7)+1)
def prime_factor(n):
    if pre[n]==0:
        i=0
        val=1
        t=n
        while ar[i]*ar[i]<=n and n>1:
            c=0
            while n%ar[i]==0:
                c+=1
                n/=ar[i]
            c=c%2
            val=int(val*(ar[i]**c))        
            i+=1
        if n>1:
            val*=int(n)
        pre[t]=val
        return val
    return pre[n]

tc=inpi()
while tc:
    n,k=inpm()
    li=inpl()
    p_s(10**4)
    arr=[]
    omap={}
    val=prime_factor(li[0])
    omap[val]=1
    arr.append(omap)
    c=1
    for i in ra(1,n):
        val=prime_factor(li[i])
        if val in arr[-1]:
            temp={}
            temp[val]=1
            c+=1
            arr.append(temp)
        else:
            arr[-1][val]=1
    P(l(arr))
    tc-=1
    
    