#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;typedef long long LL;#define INF 0x3f3f3f3f#define N 100005#define MAX 10000005int solve;struct node{ int left; int right; int flag; int value; int sum;};node tree[N*4];bool prime[MAX]; void prim_num() { int i,j; prime[1] = prime[0] = false; for(i=2; i<MAX; i++) prime[i] = true; for(i=2; i<MAX; i++) { for(j=i+i; j<MAX; j+=i) { if(prime[i]) prime[j]=false; } }}void build_tree(int l, int r, int p){ tree[p].left = l; tree[p].right = r; tree[p].flag = 0; if(l == r) { scanf("%d", &tree[p].value); tree[p].flag = 1; return ; } int mid = (tree[p].left + tree[p].right) / 2; build_tree(l, mid, p*2); build_tree(mid+1, r, p*2+1);}void add(int k, int p, int value){ if(tree[p].left == k && tree[p].right == k) { tree[p].value += value; return ; } if(tree[p].flag) { tree[p].flag = 0; tree[p*2].flag = 1; tree[p*2+1].flag = 1; tree[p*2].value = tree[p].value; tree[p*2+1].value = tree[p].value; } int mid = (tree[p].left + tree[p].right) / 2; if(k<=mid) add(k, p*2, value); else add(k, p*2+1, value);}void Replace(int l, int r, int p, int value){ if(tree[p].left == l && tree[p].right == r) { tree[p].flag = 1; tree[p].value = value; return ; } if(tree[p].flag) { tree[p].flag = 0; tree[p*2].flag = 1; tree[p*2+1].flag = 1; tree[p*2].value = tree[p].value; tree[p*2+1].value = tree[p].value; } int mid = (tree[p].right + tree[p].left) / 2; if(r<=mid) Replace(l, r, p*2, value); else if(l >=mid+1) Replace(l, r, p*2+1, value); else { Replace(l, mid, p*2, value); Replace(mid+1, r, p*2+1, value); }}void Query(int l, int r, int p){ if(tree[p].left == l && tree[p].right == r && tree[p].flag) { if(prime[tree[p].value]) solve += (tree[p].right - tree[p].left + 1); return ; } if(tree[p].flag) { tree[p*2].flag = 1; tree[p*2+1].flag = 1; tree[p*2].value = tree[p].value; tree[p*2+1].value = tree[p].value; } int mid = (tree[p].right + tree[p].left) / 2; if(r<=mid) Query(l, r, p*2); else if(l >= mid+1) Query(l, r, p*2+1); else { Query(l, mid, p*2); Query(mid+1, r, p*2+1); }}int main(){ char str[100]; prim_num(); int T, n, m , ans, tmp, l, r, d, value; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); build_tree(1, n, 1); for(int i=0; i<m; i++) { int k; scanf("%s", &str); for(k=0; str[k]!=' '; k++) if(str[k] >='A' && str[k]<='Z') break; if(str[k] == 'A') { scanf("%d%d",&value, &d); add(d, 1, value); } else if(str[k] == 'R') { scanf("%d%d%d", &value, &l, &r); Replace(l, r, 1, value); } else { solve = 0; scanf("%d%d", &l, &r); Query(l, r, 1); printf("%dn", solve); } } } return 0;}
