#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=12345678;
bool notPrime[maxn];
int ai[123456];
struct he
{
    int l,r,lazy,ans;
} Sky[123456*4];
void BuildTree(int l,int r,int now)
{
    Sky[now].l=l;
    Sky[now].r=r;
    Sky[now].lazy=0;
    Sky[now].ans=0;
    if(l==r)
    {
        Sky[now].lazy=ai[l];
        if(!notPrime[Sky[now].lazy])Sky[now].ans=1;
        else Sky[now].ans=0;
        return;
    }
    int mid=(l+r)>>1;
    BuildTree(l,mid,now<<1);
    BuildTree(mid+1,r,now<<1|1);
    Sky[now].ans=Sky[now<<1].ans+Sky[now<<1|1].ans;
}

void PushDown(int x)
{
    if(Sky[x].lazy==0)return;
    int ls=x<<1;
    int rs=x<<1|1;
    if(!notPrime[Sky[x].lazy])
    {
        Sky[ls].ans=Sky[ls].r-Sky[ls].l+1;
        Sky[rs].ans=Sky[rs].r-Sky[rs].l+1;
    }
    else
    {
        Sky[ls].ans=0;
        Sky[rs].ans=0;
    }
    Sky[ls].lazy=Sky[x].lazy;
    Sky[rs].lazy=Sky[x].lazy;
    Sky[x].lazy=0;
}//单点
void Update1(int id,int v,int now)
{
    if(Sky[now].l==id&&Sky[now].r==id)
    {
        Sky[now].lazy+=v;
        if(!notPrime[Sky[now].lazy])Sky[now].ans=1;
        else Sky[now].ans=0;
        return;
    }
    PushDown(now);
    int mid=(Sky[now].l+Sky[now].r)>>1;
    if(id<=mid)
    {
        Update1(id,v,now<<1);
    }
    else
    {
        Update1(id,v,now<<1|1);
    }
    Sky[now].ans=Sky[now<<1].ans+Sky[now<<1|1].ans;
}
//区间
void Update2(int l,int r,int now,int v)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {
        Sky[now].lazy=v;
        if(!notPrime[v])
        {
            Sky[now].ans=r-l+1;
        }
        else
        {
            Sky[now].ans=0;
        }
        return;
    }
    PushDown(now);
    int mid=(Sky[now].l+Sky[now].r)>>1;
    if(r<=mid)
    {
        Update2(l,r,now<<1,v);
    }
    else if(l>mid)
    {
        Update2(l,r,now<<1|1,v);
    }
    else
    {
        Update2(l,mid,now<<1,v);
        Update2(mid+1,r,now<<1|1,v);
    }
    Sky[now].ans=Sky[now<<1].ans+Sky[now<<1|1].ans;
}
int  Query(int l,int r,int now)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {

        return Sky[now].ans;
    }
    PushDown(now);
    int mid=(Sky[now].l+Sky[now].r)>>1;
    int o1=0,o2=0;
    if(r<=mid)
    {
        o1=Query(l,r,now<<1);
    }
    else if(l>mid)
    {
        o2=Query(l,r,now<<1|1);
    }
    else
    {
        o1=Query(l,mid,now<<1);
        o2=Query(mid+1,r,now<<1|1);
    }
    return o1+o2;
}
int T,N,Q;
char OP[10];
void init()
{
    scanf("%d%d",&N,&Q);
    for(int i=1; i<=N; i++)
    {
        scanf("%d",&ai[i]);

    }
    BuildTree(1,N,1);
}
void play()
{
    int l,r,v;
    while(Q--)
    {
        scanf("%s",OP+1);
        scanf("%d%d",&v,&l);
        if(OP[1]=='A')
        {
            Update1(l,v,1);
        }
        else if(OP[1]=='R')
        {
            scanf("%d",&r);
            Update2(l,r,1,v);
        }
        else
        {
            int ans=Query(v,l,1);
            printf("%d\n",ans);
        }
    }
}
int main()
{
    memset(notPrime,0,sizeof(notPrime));
    notPrime[1]=1;
    for(int i = 2; i*i <= maxn; i++)
    {
        if(!notPrime[i])
        {
            for(int j = i*i; j <= maxn; j += i)
            {
                notPrime[j] = true;
            }
        }
    }
    scanf("%d",&T);

    while(T--)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}