// Arup Guha
// 9/27/2026
// Solution to COP 3503 Program 3: Counting Oranges

import java.util.*;
import java.io.*;

public class oranges {

	final public static int MAX = 10000000;
	
	public static void main(String[] args) throws Exception {
		
		// Run the prime sieve; store ints not boolean.
		int[] prime = new int[MAX+1];
		Arrays.fill(prime, 1);
		prime[0] = 0; prime[1] = 0;
		for (int i=2; i<=MAX; i++)
			for (int j=2*i; j<=MAX; j+=i)
				prime[j] = 0;
			
		FastScanner stdin = new FastScanner(System.in);
		int nC = stdin.nextInt();
		
		// Store answers here.
		StringBuffer sb = new StringBuffer();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
		
			// Get basic parameters.
			int n = stdin.nextInt();
			int q = stdin.nextInt();
			
			// We'll use two BITs.
			bit orangeCnt = new bit(n);
			bit primes = new bit(n);
			
			// Also just store the numbers...
			int[] curCnt = new int[n];
			
			// Update both bits for initial values.
			for (int i=0; i<n; i++) {
				int val = stdin.nextInt();
				curCnt[i] = val;
				orangeCnt.add(i+1, val);
				if (prime[val] == 1) primes.add(i+1, 1);
			}
			
			// Process queries.
			for (int i=0; i<q; i++) {
				int cmd = stdin.nextInt();
				
				// Change a tree.
				if (cmd == 1) {
					
					// Get command details.
					int idx = stdin.nextInt();
					int delta = stdin.nextInt();
					
					// Obtain the current value on the tree.
					int wasPrime = prime[curCnt[idx-1]];
					int isPrime = prime[curCnt[idx-1]+delta];
					
					// Change BITs and array.
					orangeCnt.add(idx, delta);
					primes.add(idx, isPrime-wasPrime);
					curCnt[idx-1] += delta;
				}
				
				// Query.
				else {
					
					// Get indexes.
					int lowIdx = stdin.nextInt();
					int highIdx = stdin.nextInt();
					
					// Get answers and add to buffer.
					long total = orangeCnt.rangeSum(lowIdx, highIdx);
					long numP = primes.rangeSum(lowIdx, highIdx);
					sb.append(total+" "+numP+"\n");
				}
			}
		}
		
		// Ta da!
		System.out.print(sb);
	}
}

class bit {

	private long[] arr;
	private int n;
	
	public bit(int myn) {
		
		// Make table size a power of 2 and big enough.
		n = 1;
		while (n<myn+5)
			n <<= 1;
			
		// So we don't have to worry about overflow.
		arr = new long[n];
	}
	
	// Adds v to index idx.
	public void add(int idx, long v) {
		while (idx < n) {
			arr[idx] += v;
			idx += (idx & (-idx));
		}
	}
	
	// Returns sum from index 1 to index idx.
	public long query(int idx) {
		long res = 0;
		while (idx > 0) {
			res += arr[idx];
			idx -= (idx & (-idx));
		}
		return res;
	}
	
	// Returns the sum of this bit from index low to index high, inclusive.
	public long rangeSum(int low, int high) {
		return query(high) - query(low-1);
	}

}

/*** Fast Scanner ***/
class FastScanner {
    BufferedReader br;
    StringTokenizer st;
	
    public FastScanner(InputStream i) {
        br = new BufferedReader(new InputStreamReader(i));
        st = new StringTokenizer("");
    }
			
    public String next() throws IOException {
        if(st.hasMoreTokens())
            return st.nextToken();
        else
            st = new StringTokenizer(br.readLine());
        return next();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    
    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }
	
    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}
