import sys
import math

def get_factors(x):
    factors = {}
    while x % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        x //= 2
    i = 3
    while i * i <= x:
        while x % i == 0:
            factors[i] = factors.get(i, 0) + 1
            x //= i
        i += 2
    if x > 1:
        factors[x] = factors.get(x, 0) + 1
    return factors

def count_divisors(x):
    if x == 0:
        return 0
    factors = get_factors(x)
    count = 1
    for exp in factors.values():
        count *= (exp + 1)
    return count

class SegmentTree:
    def __init__(self, size):
        self.N = 1
        while self.N < size:
            self.N <<= 1
        self.tree = [0] * (2 * self.N)
    
    def update(self, idx, value):
        idx += self.N - 1
        self.tree[idx] = value
        idx //= 2
        while idx >= 1:
            self.tree[idx] = math.gcd(self.tree[2*idx], self.tree[2*idx+1])
            idx //= 2
    
    def remove(self, idx):
        idx += self.N - 1
        self.tree[idx] = 0
        idx //= 2
        while idx >= 1:
            self.tree[idx] = math.gcd(self.tree[2*idx], self.tree[2*idx+1])
            idx //= 2
    
    def get_gcd(self):
        return self.tree[1] if self.N >= 1 else 0

def main():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        n, q = int(input[ptr]), int(input[ptr+1])
        ptr += 2
        a = list(map(int, input[ptr:ptr+n]))
        ptr += n
        bad = set()
        for i in range(n-1):
            if a[i] > a[i+1]:
                bad.add(i+1)
        st = SegmentTree(n)
        for i in bad:
            st.update(i, i)
        g = st.get_gcd()
        if not bad:
            print(n)
        else:
            print(count_divisors(g))
        for __ in range(q):
            p, v = int(input[ptr]), int(input[ptr+1])
            ptr += 2
            a[p-1] = v
            for i in [p-1, p]:
                if 1 <= i <= n-1:
                    if a[i-1] > a[i]:
                        bad.add(i)
                    else:
                        if i in bad:
                            bad.remove(i)
            st = SegmentTree(n)
            for i in bad:
                st.update(i, i)
            g = st.get_gcd()
            if not bad:
                print(n)
            else:
                print(count_divisors(g))

if __name__ == "__main__":
    main()