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