code:

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
#define int long long

const ll mod = 1000000007;
const ll maxn = 100055;

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;
	}
};

ll n, m, seed, vmax, a[maxn];
set<node>odt;

#define IT set<node>::iterator

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 add(ll l, ll r, ll x) {
	set<node>::iterator itr = split(r + 1), itl = split(l);
	for (register set<node>::iterator it = itl; it != itr; it++)it->v += x;
}
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));
}
struct Rank {
	int num, cnt;
	bool operator<(const Rank& a)const {
		return num < a.num;
	}
	Rank(ll num, ll cnt) :num(num), cnt(cnt) {}
};
ll rnk(ll l, ll r, ll x) {
	set<node>::iterator itr = split(r + 1), itl = split(l);
	vector<Rank>v;
	for (register set<node>::iterator i = itl; i != itr; i++) {
		v.push_back(Rank(i->v, i->r - i->l + 1));
	}
	sort(v.begin(), v.end());
	register int i;
	for (i = 0; i < v.size(); i++) {
		if (v[i].cnt < x) {
			x -= v[i].cnt;
		}
		else break;
	}
	return v[i].num;
}
ll qpow(ll x, ll y, ll p) {
	//pow(x,y) mod p
	ll r = 1;
	ll base = x % p;
	while (y) {
		if (y & 1)r = r * base % p;
		base = base * base % p;
		y >>= 1;
	}
	return r;
}
ll calp(ll l, ll r, ll x, ll y) {
	set<node>::iterator itr = split(r + 1), itl = split(l);
	register ll ans = 0;
	for (register set<node>::iterator i = itl; i != itr; i++) {
		ans = (ans + qpow(i->v, x, y) * (i->r - i->l + 1) % y) % y;
	}
	ans %= y;
	return ans;
}
ll rnd() {
	ll ret = seed;
	seed = (seed * 7 + 13) % mod;
	return ret;
}
bool prime(int x) {
	if (x == 0 || x == 1) {
		return 0;
	}
	if (x == 2 || x == 3) {
		return 1;
	}
	if (x % 6 != 1 && x % 6 != 5) {
		return 0;
	}
	for (register int i = 5; i * i <= x; i++) {
		if (x % i == 0 || x % (i + 2) == 0)return 0;
	}
	return 1;
}
int countprime(int l, int r) {
	set<node>::iterator itr = split(r + 1), itl = split(l);
	int cnt = 0;
	for (register set<node>::iterator it = itl; it != itr; it++) {
		if (prime(it->v))cnt += (it->r - it->l) + 1;
	}
	return cnt;
}
signed main() {
	int t;
	cin >> t;
a:
	odt.clear();
	int n, m;
	cin >> n >> m;
	int op, x, y, v;
	int val;
	for (register int i = 1; i <= n; i++) {
		cin >> val;
		odt.insert(node(i, i, val));
	}
	for (register int i = 1; i <= m; i++) {
		cin >> op;
		if (op == 0) {
			cin >> x >> y >> v;
			assign(x, y, v);
		}
		else {
			cin >> x >> y;
			cout << countprime(x, y) << endl;
		}
	}
	t--;
	if (t)goto a;
	return 0;
}