#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << '\n'
#define debug_arr(a , n) for(ll i = 0 ; i < n ; i++)cout << a[i] << " "
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vi vector<ll>
#define vll vector<ll>
#define inf 1000000000
#define mod 1000000007
const ll max_n = 1e5 + 9;
const ll Max_n = 1e6 + 9;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a , ll b)
{
ll prod = 1;
while(b)
{
if(b&1)
prod = (prod*a)%mod;
a = (a*a)%mod;
b >>= 1;
}
return prod;
}
ll t[4*max_n];
ll lazy[4*max_n];
ll a[max_n];
ll isprime[Max_n];
void init(){
isprime[0] = isprime[1] = 1;
for(ll i = 2 ; i*i < Max_n ; i++){
if(isprime[i] == 0){
for(ll j = i*i ; j < Max_n ; j += i){
isprime[j] = 1;
}
}
}
}
void build(ll v , ll l , ll r){
if(l == r){
t[v] = isprime[a[l]] ^ 1;
}
else
{
ll tm = (l + r) >> 1;
build(2*v , l , tm);
build(2*v + 1 , tm+1 , r);
t[v] = t[2*v] + t[2*v+1];
}
}
void update(ll v, ll tl , ll tr , ll l , ll r , ll ele){
if(lazy[v]){
t[v] = (tr - tl + 1) * (isprime[lazy[v]] ^ 1);
if(l != r){
lazy[2*v] = lazy[v];
lazy[2*v+1] = lazy[v];
}
lazy[v] = 0;
}
if(l > r){
return;
}
if(l == tl && r == tr){
t[v] = (isprime[ele] ^ 1) * (r - l + 1);
if(l != r){
lazy[2*v] = ele;
lazy[2*v+1] = ele;
}
}
else
{
ll tm = (tl + tr) >> 1;
update(2*v , tl , tm , l , min(r , tm) , ele);
update(2*v+1 , tm+1 , tr , max(l , tm+1) , r , ele);
t[v] = t[2*v] + t[2*v+1];
}
}
ll query(ll v , ll tl , ll tr , ll l , ll r){
if(lazy[v]){
t[v] = (tr - tl + 1)*(isprime[lazy[v]]^1);
if(tl != tr){
lazy[2*v] = lazy[v];
lazy[2*v+1] = lazy[v];
}
lazy[v] = 0;
}
if(l > r)return 0;
if(l == tl && r == tr){
return t[v];
}
ll tm = (tl + tr) >> 1;
return query(2*v , tl , tm , l , min(r , tm)) + query(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
}
int main()
{
int T;
cin >> T;
init();
for(int x = 1 ; x <= T ; x++){
cout << "Case " << x << ":" << endl;
ll n , q;
cin >> n >> q;
memset(a , 0 , sizeof(a));
memset(t , 0 , sizeof(t));
memset(lazy , 0 , sizeof(lazy));
for(ll i = 0 ; i < n ; i++){
cin >> a[i];
}
build(1 , 0 , n-1);
// cout << t[1] << endl;
while(q--){
ll op;
cin >> op;
if(op == 1){
ll l , r;
cin >> l >> r;
l-- , r--;
cout << query(1 , 0 , n-1 , l , r) << endl;
}
else{
ll l , r , ele;
cin >> l >> r >> ele;
l-- , r--;
update(1 , 0 , n-1 , l , r , ele);
}
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgp1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CiNkZWZpbmUgZGVidWcoeCkgY291dCA8PCAjeCA8PCAiID0gIiA8PCB4IDw8ICdcbicKI2RlZmluZSBkZWJ1Z19hcnIoYSAsIG4pIGZvcihsbCBpID0gMCA7IGkgPCBuIDsgaSsrKWNvdXQgPDwgYVtpXSA8PCAiICIKI2RlZmluZSBzcGVlZCBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApO2Npbi50aWUoMCk7Y291dC50aWUoMCkKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIHZpIHZlY3RvcjxsbD4KI2RlZmluZSB2bGwgdmVjdG9yPGxsPiAKI2RlZmluZSBpbmYgMTAwMDAwMDAwMAojZGVmaW5lIG1vZCAxMDAwMDAwMDA3Cgpjb25zdCBsbCBtYXhfbiA9IDFlNSArIDk7CmNvbnN0IGxsIE1heF9uID0gMWU2ICsgOTsKCnR5cGVkZWYgdHJlZTxsbCxudWxsX3R5cGUsbGVzczxsbD4scmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPiBpbmRleGVkX3NldDsKbGwgcG93ZXIobGwgYSAsIGxsIGIpCnsKICAgIGxsIHByb2QgPSAxOwogICAgd2hpbGUoYikKICAgIHsKICAgICAgICBpZihiJjEpCiAgICAgICAgcHJvZCA9IChwcm9kKmEpJW1vZDsKICAgICAgICBhID0gKGEqYSklbW9kOwogICAgICAgIGIgPj49IDE7CiAgICB9CiAgICByZXR1cm4gcHJvZDsKfQoKbGwgdFs0Km1heF9uXTsKbGwgbGF6eVs0Km1heF9uXTsKCmxsIGFbbWF4X25dOwpsbCBpc3ByaW1lW01heF9uXTsKdm9pZCBpbml0KCl7CiAgICBpc3ByaW1lWzBdID0gaXNwcmltZVsxXSA9IDE7CiAgICBmb3IobGwgaSA9IDIgOyBpKmkgPCBNYXhfbiA7IGkrKyl7CiAgICAgICAgaWYoaXNwcmltZVtpXSA9PSAwKXsKICAgICAgICAgICAgZm9yKGxsIGogPSBpKmkgOyBqIDwgTWF4X24gOyBqICs9IGkpewogICAgICAgICAgICAgICAgaXNwcmltZVtqXSA9IDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0Kdm9pZCBidWlsZChsbCB2ICwgbGwgbCAsIGxsIHIpewogICAgaWYobCA9PSByKXsKICAgICAgICB0W3ZdID0gaXNwcmltZVthW2xdXSBeIDE7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgbGwgdG0gPSAobCArIHIpID4+IDE7CiAgICAgICAgYnVpbGQoMip2ICwgbCAsIHRtKTsKICAgICAgICBidWlsZCgyKnYgKyAxICwgdG0rMSAsIHIpOwogICAgICAgIHRbdl0gPSB0WzIqdl0gKyB0WzIqdisxXTsKICAgIH0KfQp2b2lkIHVwZGF0ZShsbCB2LCAgbGwgdGwgLCBsbCB0ciAsIGxsIGwgLCBsbCByICwgbGwgZWxlKXsKICAgIGlmKGxhenlbdl0pewogICAgICAgIHRbdl0gPSAodHIgLSB0bCArIDEpICogKGlzcHJpbWVbbGF6eVt2XV0gXiAxKTsKICAgICAgICBpZihsICE9IHIpewogICAgICAgICAgICBsYXp5WzIqdl0gPSBsYXp5W3ZdOwogICAgICAgICAgICBsYXp5WzIqdisxXSA9IGxhenlbdl07CiAgICAgICAgfQogICAgICAgIGxhenlbdl0gPSAwOwogICAgfQogICAgaWYobCA+IHIpewogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmKGwgPT0gdGwgJiYgciA9PSB0cil7CiAgICAgICAgdFt2XSA9IChpc3ByaW1lW2VsZV0gXiAxKSAqIChyIC0gbCArIDEpOwogICAgICAgIGlmKGwgIT0gcil7CiAgICAgICAgICAgIGxhenlbMip2XSA9IGVsZTsKICAgICAgICAgICAgbGF6eVsyKnYrMV0gPSBlbGU7CiAgICAgICAgfQogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGxsIHRtID0gKHRsICsgdHIpID4+IDE7CiAgICAgICAgdXBkYXRlKDIqdiAsIHRsICwgdG0gLCBsICwgbWluKHIgLCB0bSkgLCBlbGUpOwogICAgICAgIHVwZGF0ZSgyKnYrMSAsIHRtKzEgLCB0ciAsIG1heChsICwgdG0rMSkgLCByICwgZWxlKTsKICAgICAgICB0W3ZdID0gdFsyKnZdICsgdFsyKnYrMV07CiAgICB9Cn0KbGwgcXVlcnkobGwgdiAsIGxsIHRsICwgbGwgdHIgLCBsbCBsICwgbGwgcil7CiAgICBpZihsYXp5W3ZdKXsKICAgICAgICB0W3ZdID0gKHRyIC0gdGwgKyAxKSooaXNwcmltZVtsYXp5W3ZdXV4xKTsKICAgICAgICBpZih0bCAhPSB0cil7CgkJCWxhenlbMip2XSA9IGxhenlbdl07CiAgICAgICAgICAgIGxhenlbMip2KzFdID0gbGF6eVt2XTsKICAgICAgICB9CiAgICAgICAgbGF6eVt2XSA9IDA7CiAgICB9CiAgICBpZihsID4gcilyZXR1cm4gMDsKICAgIGlmKGwgPT0gdGwgJiYgciA9PSB0cil7CiAgICAgICAgcmV0dXJuIHRbdl07CiAgICB9CiAgICBsbCB0bSA9ICh0bCArIHRyKSA+PiAxOwogICAgcmV0dXJuIHF1ZXJ5KDIqdiAsIHRsICwgdG0gLCBsICwgbWluKHIgLCB0bSkpICsgcXVlcnkoMip2KzEgLCB0bSsxICwgdHIgLCBtYXgobCAsIHRtKzEpICwgcik7Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgVDsKICAgIGNpbiA+PiBUOwogICAgaW5pdCgpOwoKICAgIAogICAgZm9yKGludCB4ID0gMSA7IHggPD0gVCA7IHgrKyl7CiAgICAgICAgY291dCA8PCAiQ2FzZSAiIDw8IHggPDwgIjoiIDw8IGVuZGw7CiAgICAgICAgbGwgbiAsIHE7CiAgICAgICAgY2luID4+IG4gPj4gcTsKICAgICAgICBtZW1zZXQoYSAsIDAgLCBzaXplb2YoYSkpOwogICAgICAgIG1lbXNldCh0ICwgMCAsIHNpemVvZih0KSk7CiAgICAgICAgbWVtc2V0KGxhenkgLCAwICwgc2l6ZW9mKGxhenkpKTsKICAgICAgICBmb3IobGwgaSA9IDAgOyBpIDwgbiA7IGkrKyl7CiAgICAgICAgICAgIGNpbiA+PiBhW2ldOwogICAgICAgIH0KICAgICAgICBidWlsZCgxICwgMCAsIG4tMSk7CiAgICAgICAgLy8gY291dCA8PCB0WzFdIDw8IGVuZGw7CiAgICAgICAgd2hpbGUocS0tKXsKICAgICAgICAgICAgbGwgb3A7CiAgICAgICAgICAgIGNpbiA+PiBvcDsKICAgICAgICAgICAgaWYob3AgPT0gMSl7CiAgICAgICAgICAgICAgICBsbCBsICwgcjsKICAgICAgICAgICAgICAgIGNpbiA+PiBsID4+IHI7CiAgICAgICAgICAgICAgICBsLS0gLCByLS07CiAgICAgICAgICAgICAgICBjb3V0IDw8IHF1ZXJ5KDEgLCAwICwgbi0xICwgbCAsIHIpIDw8IGVuZGw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgIGxsIGwgLCByICwgZWxlOwogICAgICAgICAgICAgICAgY2luID4+IGwgPj4gciA+PiBlbGU7CiAgICAgICAgICAgICAgICBsLS0gLCByLS07CiAgICAgICAgICAgICAgICB1cGRhdGUoMSAsIDAgLCBuLTEgLCBsICwgciAsIGVsZSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=