import sys
import math

def get_divisors(x):
    divisors = set()
    for i in range(1, int(math.isqrt(x)) + 1):
        if x % i == 0:
            divisors.add(i)
            divisors.add(x // i)
    return divisors

def solve():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    T = int(data[idx])
    idx += 1
    for _ in range(T):
        n = int(data[idx])
        q = int(data[idx + 1])
        idx += 2
        a = list(map(int, data[idx:idx + n]))
        idx += n
        
        # Initial calculation
        S = set()
        for s in range(n - 1):
            if a[s] > a[s + 1]:
                S.add(s + 1)  # 1-based positions
        
        if not S:
            print(n)
        else:
            g = 0
            for s in S:
                g = math.gcd(g, s)
            divisors = get_divisors(g)
            print(len(divisors))
        
        # Process queries
        for _ in range(q):
            p = int(data[idx])  # 1-based
            v = int(data[idx + 1])
            idx += 2
            a[p - 1] = v
            
            # Update S for position p-1 and p
            if p > 1:
                prev = a[p - 2] > a[p - 1]
                curr = a[p - 2] > a[p - 1]
                if prev and not curr:
                    S.discard(p - 1)
                elif not prev and curr:
                    S.add(p - 1)
            if p < n:
                prev = a[p - 1] > a[p]
                curr = a[p - 1] > a[p]
                if prev and not curr:
                    S.discard(p)
                elif not prev and curr:
                    S.add(p)
            
            if not S:
                print(n)
            else:
                g = 0
                for s in S:
                    g = math.gcd(g, s)
                divisors = get_divisors(g)
                print(len(divisors))

if __name__ == '__main__':
    solve()