#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1E4 + 10, MAXK = 9;

ll expMod(ll e, ll n, ll p){
	if (n < 0)
		return 1;
	ll ret = 1;
	for (; n; n >>= 1, e = e * e % p)
		if (n & 1)
			ret = ret * e % p;
	return ret;
}

struct SegmentTree{
	int pro[MAXN << 2], prol[MAXN << 2];;
	ll cnt[MAXN << 2][MAXK], cntl[MAXN << 2][MAXK];

	int k, d[MAXK], dc[MAXK];

	int n, p, phi, *origin;
	int L, R, C;
	ll add[MAXK];

	inline void push(int u, int len, int tC, ll *tadd){
		pro[u] = pro[u] * expMod(tC, len, p) % p;
		prol[u] = prol[u] * (ll)tC % p;
		for (int i = 0; i < k; ++i){
			cnt[u][i] += tadd[i] * len;
			cntl[u][i] += tadd[i];
		}
	}

	inline void pushDown(int u, int len){
		push(u << 1, len >> 1, prol[u], cntl[u]);
		push(u << 1 | 1, len + 1 >> 1, prol[u], cntl[u]);
		prol[u] = 1, memset(cntl[u], 0, sizeof(cntl[0]));
	}

	inline void pushUp(int u){
		pro[u] = pro[u << 1] * (ll)pro[u << 1 | 1] % p;
		for (int i = 0; i < k; ++i)
			cnt[u][i] = cnt[u << 1][i] + cnt[u << 1 | 1][i];
	}

	void _build(int u, int l, int r){
		prol[u] = 1, memset(cntl[u], 0, sizeof(cntl[0]));
		if (r - l == 1){
			int t = origin[l];
			memset(cnt[u], 0, sizeof(cnt[u]));
			if (t){
				for (int i = 0; i < k; ++i){
					for (; t % d[i] == 0; t /= d[i])
						++cnt[u][i];
				}
			}
			pro[u] = t;
			return;
		}
		int m = l + r >> 1;
		_build(u << 1, l, m);
		_build(u << 1 | 1, m, r);
		pushUp(u);
	}

	void _update(int u, int l, int r){
		if (L <= l && r <= R){
			push(u, r - l, C, add);
			return;
		}
		pushDown(u, r - l);
		int m = l + r >> 1;
		if (L < m)
			_update(u << 1, l, m);
		if (m < R)
			_update(u << 1 | 1, m, r);
		pushUp(u);
	}

	void _query(int u, int l, int r){
		if (L <= l && r <= R){
			C = C * (ll)pro[u] % p;
			for (int i = 0; i < k; ++i)
				add[i] += cnt[u][i];
			return;
		}
		pushDown(u, r - l);
		int m = l + r >> 1;
		if (L < m)
			_query(u << 1, l, m);
		if (m < R)
			_query(u << 1 | 1, m, r);
		pushUp(u);
	}

	void build(int tn, int tp, int *ta){
		n = tn, p = phi = tp, origin = ta;

		int i = 2;
		for (k = 0; i * i <= tp; ++i)
			if (tp % i == 0){
				phi = phi / i * (i - 1);
				for (; tp % i == 0; tp /= i)
				d[k++] = i;
			}
		if (tp > 1){
			phi = phi / tp * (tp - 1);
			d[k++] = tp;
		}

		_build(1, 1, n + 1);
	}

	void multi(int tl, int tr, int tc){
		L = tl, R = tr + 1, C = tc;
		memset(add, 0, sizeof(add));
		if (tc){
			for (int i = 0; i < k; ++i){
				for (; C % d[i] == 0; C /= d[i])
					++add[i];
			}
		}
		_update(1, 1, n + 1);
	}

	void divide(int tl, int tr, int tc){
		L = tl, R = tr + 1, C = tc;
		memset(add, 0, sizeof(add));
		for (int i = 0; i < k; ++i){
			for (; C % d[i] == 0; C /= d[i])
				--add[i];
		}
		C = expMod(C, phi - 1, p);
		_update(1, 1, n + 1);
	}

	int query(int tl, int tr){
		L = tl, R = tr + 1;
		C = 1;
		memset(add, 0, sizeof(add));
		_query(1, 1, n + 1);
		for (int i = 0; i < k; ++i)
			C = C * expMod(d[i], add[i], p) % p;
		return C;
	}
}tree;

int a[MAXN];

int main(){
	int cas;
	scanf("%d", &cas);
	for (int casi = 1; casi <= cas; ++casi){
		printf("Case #%d:\n", casi);

		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		tree.build(n, m, a);

		int q, l, r, x;
		char com[5];
		scanf("%d", &q);
		for (int i = 0; i < q; ++i){
			scanf("%s%d%d", com, &l, &r);
			if (com[0] == 'Q')
				printf("%d\n", tree.query(l, r));
			else{
				scanf("%d", &x);
				if (com[0] == 'M')
					tree.multi(l, r, x);
				else
					tree.divide(l, r, x);
			}
		}
	}
	return 0;
}