#include<bits/stdc++.h>
using namespace std;
#define TIPS "ctjzm"
#define IT set<node>::iterator
typedef long long TYPE;

int prime[10000007];
bool f[10000007];

void sieve(){
    int n=10000000;  
    f[0]=f[1]=1;
    int cnt=1;
    for(int i=2;i<=n;i++){
        if(!f[i])
            prime[cnt++]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            f[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }   
    }
}//线性筛

struct node{
    unsigned int l,r;
    mutable TYPE v;
    node(unsigned int left,unsigned int right=0,TYPE value=0);
};
bool operator<(node a,node b){
    return a.l<b.l;
}
node::node(unsigned int left,unsigned int right,TYPE value){
    l=left;
    r=right;
    v=value;
}
set<node>odt; 
inline IT split(unsigned int p){
    IT it=odt.lower_bound(node(p));
    if(it!=odt.end()&&it->l==p)
        return it;
    --it;
    unsigned r=it->r,l=it->l;
    TYPE v=it->v;
    odt.erase(it);
    odt.insert(node(l,p-1,v));
    return odt.insert(node(p,r,v)).first;   
}//珂朵莉树核心——分裂操作
inline void assign(int l, int r, int v) {
    IT itr=split(r+1),itl=split(l);
    odt.erase(itl, itr);
    odt.insert(node(l, r, v));
}//操作1+珂朵莉树核心——推平操作
//祖传珂朵莉树模板↑
inline int getsum(int l,int r){
    long long sum=0;
    IT itr=split(r+1),itl=split(l);
    for(IT it=itl;it!=itr;++it)
        if(!f[it->v])
            sum+=it->r-it->l+1;
    return sum;        
}//操作2，统计素数

int n,m,x,y,z,t;
int ch;
int main(){
    ios::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
    sieve();//预处理
    cin>>t;
    for(int T=1;T<=t;++T){
        cout<<"Case "<<T<<":\n";
        cin>>n>>m;
        for(unsigned i=1;i<=n;++i){
            int t;
            cin>>t;
            odt.insert(node(i,i,t));
        }
        for(unsigned i=1;i<=m;++i){
            cin>>ch;
            if(!ch){
                cin>>x>>y>>z;
                assign(x,y,z);
            }
            else{
                cin>>x>>y;
                cout<<getsum(x,y)<<endl;
            }
        }
    }
    return 0;//好习惯
}