code:

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
#define int long long

struct node {
	ll l, r;
	mutable ll v;
	node(ll L, ll R = 0, ll V = 0) : l(L), r(R), v(V) {}
	bool operator<(const node& a)const {
		return l < a.l;
	}
};

set<node>odt;

set<node>::iterator split(int pos) {
	set<node>::iterator it = odt.lower_bound(node(pos));
	if (it != odt.end() && it->l == pos)return it;
	it--;
	if (it->r < pos)return odt.end();
	ll l = it->l;
	ll r = it->r;
	ll v = it->v;
	odt.erase(it);
	odt.insert(node(l, pos - 1, v));
	return odt.insert(node(pos, r, v)).first;
}
void assign(ll l, ll r, ll x) {
	set<node>::iterator itr = split(r + 1), itl = split(l);
	odt.erase(itl, itr);
	odt.insert(node(l, r, x));
}
int n, q;
int a_i, op, x, y, v;

const int N = 2e6 + 10;
int prime[N], pcnt; bool not_prime[N];
void eular() {
	not_prime[0] = not_prime[1] = true;
	for (int i = 2; i <= N; i++) {
		if (!not_prime[i]) {
			prime[++pcnt] = i;
		}
		for (int j = 1; j <= pcnt && i * prime[j] <= N; j++) {
			not_prime[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
	return;
}
int Query(int l, int r) {
	set<node>::iterator ir = split(r + 1), il = split(l);
	int ans = 0;
	for (set<node>::iterator it = il; it != ir; ++it) {
		if (!not_prime[it->v])ans += (it->r - it->l + 1);
	}
	return ans;
}
void query(int l, int r) {
	set<node>::iterator ir = split(r + 1), il = split(l);
	for (set<node>::iterator it = il; it != ir; ++it) {
		printf("[%lld,%lld,%lld]\n", it->l, it->r, it->v);
	}
}
void solve(int _Case) {
	odt.clear();
	printf("Case %lld\n",_Case);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a_i);
		odt.insert(node(i, i, a_i));
	}
	for (register int i = 1; i <= q; i++) {
		//query(1,n);
		scanf("%lld", &op);
		if (op == 0) {
			scanf("%lld%lld&lld", &x, &y, &v);
			assign(x, y, v);
		}
		else {
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", Query(x, y));
		}
	}
}
signed main() {
	eular();
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++)solve(i);
}