import sys
import math

def precompute_divisors(n):
    divisors = [[] for _ in range(n+1)]
    for i in range(1, n):
        for j in range(i, n, i):
            divisors[j].append(i)
    return divisors

def main():
    import sys
    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
        modifications = []
        for _ in range(q):
            p = int(data[idx]) - 1  # 0-based index
            v = int(data[idx+1])
            modifications.append((p, v))
            idx += 2
        
        # Precompute divisors
        divisors = precompute_divisors(n)
        
        # Initial bad positions
        B = []
        for i in range(n-1):
            if a[i] > a[i+1]:
                B.append(i+1)  # 1-based index
        
        m = len(B)
        count_k = [0] * (n + 1)
        freq = [0] * (n + 1)
        
        for i in B:
            for d in divisors[i]:
                count_k[d] += 1
                if count_k[d] == 1:
                    freq[1] += 1
                else:
                    freq[count_k[d]] += 1
                    freq[count_k[d]-1] -= 1
        
        if m == 0:
            print(n)
        else:
            print(freq[m])
        
        for p, v in modifications:
            a[p] = v
            # Check p and p+1
            positions_to_check = []
            if p > 0:
                positions_to_check.append(p)
            if p < n-1:
                positions_to_check.append(p+1)
            
            added = []
            removed = []
            for pos in positions_to_check:
                one_b = a[pos-1] > a[pos]
                two_b = a[pos] > a[pos+1]
                if one_b:
                    if pos not in B:
                        B.append(pos)
                        added.append(pos)
                else:
                    if pos in B:
                        B.remove(pos)
                        removed.append(pos)
                if two_b:
                    if pos+1 not in B:
                        B.append(pos+1)
                        added.append(pos+1)
                else:
                    if pos+1 in B:
                        B.remove(pos+1)
                        removed.append(pos+1)
            
            for pos in added:
                for d in divisors[pos]:
                    freq[count_k[d]] -= 1
                    count_k[d] += 1
                    freq[count_k[d]] += 1
            for pos in removed:
                for d in divisors[pos]:
                    freq[count_k[d]] -= 1
                    count_k[d] -= 1
                    freq[count_k[d]] += 1
            
            m = len(B)
            if m == 0:
                print(n)
            else:
                print(freq[m])

if __name__ == "__main__":
    main()