#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
typedef pair<int, int>pr;
#define all(i) i.begin() , i.end()
#define ft first
#define sn second
#define pb push_back
#define dbg cout<<"rony\n"
#define en "\n"
#define MAXN 100010
#define inf 1e6+5
const ll mod = 1e9 + 7;
int n, c, q;
int a[MAXN];
struct SegmentTree
{
struct node
{
int preval, sufval, precnt, sufcnt, an, suru, ses;
void init(int l, int r)
{
suru = l, ses = r;
if (l == r) {
preval = sufval = a[l];
an = precnt = sufcnt = 1;
}
}
} g[4 * MAXN], ans;
node fill_cn(int l, int r, node B, node C)
{
node A;
if (B.preval == -1) {
return C;
}
if (C.preval == -1) return B;
if (B.preval == C.sufval) {
A.preval = B.preval; A.sufval = B.sufval;
A.precnt = B.precnt + C.precnt;
A.sufcnt = B.sufcnt + C.sufcnt;
A.an = A.precnt;
}
else if (B.preval == B.sufval && B.sufval == C.preval) {
A.preval = B.preval; A.sufval = C.sufval;
A.precnt = B.precnt + C.precnt;
A.sufcnt = C.sufcnt;
A.an = max({B.an, C.an, A.precnt});
}
else if (B.sufval == C.preval && C.sufval == C.preval) {
A.preval = B.preval; A.sufval = B.sufval;
A.precnt = B.precnt; A.sufcnt = B.sufcnt + C.precnt;
A.an = max({B.an, C.an, A.sufcnt});
}
else if (B.sufval == C.preval) {
A.preval = B.preval; A.sufval = C.sufval;
A.precnt = B.precnt; A.sufcnt = C.sufcnt;
A.an = max({B.an, C.an, B.sufcnt + C.precnt });
}
else {
A.preval = B.preval; A.sufval = C.sufval;
A.precnt = B.precnt; A.sufcnt = C.sufcnt;
A.an = max({B.an, C.an, B.sufcnt, C.precnt});
}
return A;
}
void build(int cn, int l, int r)
{
g[cn].init(l, r);
if (l == r) return ;
int md = l + (r - l) / 2;
build(cn * 2, l, md);
build(cn * 2 + 1, md + 1, r);
g[cn] = fill_cn( l, r, g[cn * 2], g[cn * 2 + 1]);
g[cn].suru = l; g[cn].ses = r;
}
node makend()
{
node A;
A.preval = A.sufval = A.precnt = A.sufcnt = A.an = -1;
return A;
}
node query(int cn, int l, int r)
{
int x = g[cn].suru;
int y = g[cn].ses;
if (y < l || x > r ) {
return makend();
}
if (l <= x && y <= r) {
return g[cn];
}
node _1 = query( cn * 2, l, r);
node _2 = query(cn * 2 + 1, l, r);
return fill_cn(x, y, _1, _2);
}
} stre;
void solve()
{
cin >> n >> c >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
stre.build(1, 1, n);
// dbg; dbg;
while (q--)
{
int x, y;
cin >> x >> y;
stre.ans = stre.query(1, x, y);
cout << stre.ans.an << en;
}
// stre.ans = stre.query(1, 7, 7);
// cout << stre.ans.an << en;
}
int main()
{
IOS;
ll t;
t = 1;
cin >> t;
ll c = 0;
while ( t-- )
{
cout << "Case " << ++c << ":\n";
solve();
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKI2RlZmluZSBJT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgIGNpbi50aWUoMCk7IGNvdXQudGllKDApOwoKCiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKdHlwZWRlZiB0cmVlPGludCwgbnVsbF90eXBlLCBsZXNzPGludD4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+b3JkZXJfc2V0Owp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+cHI7CiNkZWZpbmUgYWxsKGkpICAgICBpLmJlZ2luKCkgLCBpLmVuZCgpCiNkZWZpbmUgZnQgICAgIGZpcnN0CiNkZWZpbmUgc24gICAgIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawoKI2RlZmluZSBkYmcgY291dDw8InJvbnlcbiIKI2RlZmluZSBlbiAiXG4iCgojZGVmaW5lIE1BWE4gMTAwMDEwCiNkZWZpbmUgaW5mIDFlNis1CmNvbnN0IGxsIG1vZCA9IDFlOSArIDc7CgppbnQgbiwgYywgcTsKaW50IGFbTUFYTl07CgpzdHJ1Y3QgU2VnbWVudFRyZWUKewogICAgc3RydWN0IG5vZGUKICAgIHsKICAgICAgICBpbnQgcHJldmFsLCBzdWZ2YWwsIHByZWNudCwgc3VmY250LCBhbiwgc3VydSwgc2VzOwogICAgICAgIHZvaWQgaW5pdChpbnQgbCwgaW50IHIpCiAgICAgICAgewogICAgICAgICAgICBzdXJ1ID0gbCwgc2VzID0gcjsKICAgICAgICAgICAgaWYgKGwgPT0gcikgewogICAgICAgICAgICAgICAgcHJldmFsID0gc3VmdmFsID0gYVtsXTsKICAgICAgICAgICAgICAgIGFuID0gcHJlY250ID0gc3VmY250ID0gMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0gZ1s0ICogTUFYTl0sIGFuczsKCiAgICBub2RlIGZpbGxfY24oaW50IGwsIGludCByLCBub2RlIEIsIG5vZGUgQykKICAgIHsKICAgICAgICBub2RlIEE7CgogICAgICAgIGlmIChCLnByZXZhbCA9PSAtMSkgewogICAgICAgICAgICByZXR1cm4gQzsKICAgICAgICB9CiAgICAgICAgaWYgKEMucHJldmFsID09IC0xKSByZXR1cm4gQjsKICAgICAgICBpZiAoQi5wcmV2YWwgPT0gQy5zdWZ2YWwpIHsKICAgICAgICAgICAgQS5wcmV2YWwgPSBCLnByZXZhbDsgQS5zdWZ2YWwgPSBCLnN1ZnZhbDsKICAgICAgICAgICAgQS5wcmVjbnQgPSBCLnByZWNudCArIEMucHJlY250OwogICAgICAgICAgICBBLnN1ZmNudCA9IEIuc3VmY250ICsgQy5zdWZjbnQ7CiAgICAgICAgICAgIEEuYW4gPSBBLnByZWNudDsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZiAoQi5wcmV2YWwgPT0gQi5zdWZ2YWwgJiYgQi5zdWZ2YWwgPT0gQy5wcmV2YWwpIHsKICAgICAgICAgICAgQS5wcmV2YWwgPSBCLnByZXZhbDsgQS5zdWZ2YWwgPSBDLnN1ZnZhbDsKICAgICAgICAgICAgQS5wcmVjbnQgPSBCLnByZWNudCArIEMucHJlY250OwogICAgICAgICAgICBBLnN1ZmNudCA9IEMuc3VmY250OwogICAgICAgICAgICBBLmFuID0gbWF4KHtCLmFuLCBDLmFuLCBBLnByZWNudH0pOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmIChCLnN1ZnZhbCA9PSBDLnByZXZhbCAmJiBDLnN1ZnZhbCA9PSBDLnByZXZhbCkgewogICAgICAgICAgICBBLnByZXZhbCA9IEIucHJldmFsOyBBLnN1ZnZhbCA9IEIuc3VmdmFsOwogICAgICAgICAgICBBLnByZWNudCA9IEIucHJlY250OyBBLnN1ZmNudCA9IEIuc3VmY250ICsgQy5wcmVjbnQ7CiAgICAgICAgICAgIEEuYW4gPSBtYXgoe0IuYW4sIEMuYW4sIEEuc3VmY250fSk7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYgKEIuc3VmdmFsID09IEMucHJldmFsKSB7CiAgICAgICAgICAgIEEucHJldmFsID0gQi5wcmV2YWw7IEEuc3VmdmFsID0gQy5zdWZ2YWw7CiAgICAgICAgICAgIEEucHJlY250ID0gQi5wcmVjbnQ7IEEuc3VmY250ID0gQy5zdWZjbnQ7CiAgICAgICAgICAgIEEuYW4gPSBtYXgoe0IuYW4sIEMuYW4sIEIuc3VmY250ICsgQy5wcmVjbnQgfSk7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBBLnByZXZhbCA9IEIucHJldmFsOyBBLnN1ZnZhbCA9IEMuc3VmdmFsOwogICAgICAgICAgICBBLnByZWNudCA9IEIucHJlY250OyBBLnN1ZmNudCA9IEMuc3VmY250OwoKICAgICAgICAgICAgQS5hbiA9IG1heCh7Qi5hbiwgQy5hbiwgQi5zdWZjbnQsIEMucHJlY250fSk7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gQTsKICAgIH0KCiAgICB2b2lkIGJ1aWxkKGludCBjbiwgaW50IGwsIGludCByKQogICAgewogICAgICAgIGdbY25dLmluaXQobCwgcik7CiAgICAgICAgaWYgKGwgPT0gcikgcmV0dXJuIDsKICAgICAgICBpbnQgbWQgPSBsICsgKHIgLSBsKSAvIDI7CiAgICAgICAgYnVpbGQoY24gKiAyLCBsLCBtZCk7CiAgICAgICAgYnVpbGQoY24gKiAyICsgMSwgbWQgKyAxLCByKTsKCiAgICAgICAgZ1tjbl0gPSBmaWxsX2NuKCBsLCByLCBnW2NuICogMl0sIGdbY24gKiAyICsgMV0pOwogICAgICAgIGdbY25dLnN1cnUgPSBsOyBnW2NuXS5zZXMgPSByOwogICAgfQoKICAgIG5vZGUgbWFrZW5kKCkKICAgIHsKICAgICAgICBub2RlIEE7CiAgICAgICAgQS5wcmV2YWwgPSBBLnN1ZnZhbCA9IEEucHJlY250ID0gQS5zdWZjbnQgPSBBLmFuID0gLTE7CiAgICAgICAgcmV0dXJuIEE7CiAgICB9CgogICAgbm9kZSBxdWVyeShpbnQgY24sIGludCBsLCBpbnQgcikKICAgIHsKICAgICAgICBpbnQgeCA9IGdbY25dLnN1cnU7CiAgICAgICAgaW50IHkgPSBnW2NuXS5zZXM7CiAgICAgICAgaWYgKHkgPCBsIHx8IHggPiByICkgewoKICAgICAgICAgICAgcmV0dXJuIG1ha2VuZCgpOwogICAgICAgIH0KICAgICAgICBpZiAobCA8PSB4ICYmIHkgPD0gcikgewoKICAgICAgICAgICAgcmV0dXJuIGdbY25dOwogICAgICAgIH0KICAgICAgICBub2RlIF8xID0gcXVlcnkoIGNuICogMiwgbCwgcik7CiAgICAgICAgbm9kZSBfMiA9IHF1ZXJ5KGNuICogMiArIDEsIGwsIHIpOwogICAgICAgIHJldHVybiBmaWxsX2NuKHgsIHksIF8xLCBfMik7CiAgICB9Cgp9IHN0cmU7Cgp2b2lkIHNvbHZlKCkKewogICAgY2luID4+IG4gPj4gYyA+PiBxOwoKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgIGNpbiA+PiBhW2ldOwogICAgfQoKICAgIHN0cmUuYnVpbGQoMSwgMSwgbik7CiAgICAvLyBkYmc7IGRiZzsKICAgIHdoaWxlIChxLS0pCiAgICB7CiAgICAgICAgaW50IHgsIHk7CiAgICAgICAgY2luID4+IHggPj4geTsKICAgICAgICBzdHJlLmFucyA9IHN0cmUucXVlcnkoMSwgeCwgeSk7CiAgICAgICAgY291dCA8PCBzdHJlLmFucy5hbiA8PCBlbjsKICAgIH0KICAgIC8vIHN0cmUuYW5zID0gc3RyZS5xdWVyeSgxLCA3LCA3KTsKICAgIC8vIGNvdXQgPDwgc3RyZS5hbnMuYW4gPDwgZW47Cgp9CmludCBtYWluKCkKewogICAgSU9TOwogICAgbGwgdDsKICAgIHQgPSAxOwogICAgY2luID4+IHQ7CgogICAgbGwgYyA9IDA7CiAgICB3aGlsZSAoIHQtLSApCiAgICB7CiAgICAgICAgY291dCA8PCAiQ2FzZSAiIDw8ICsrYyA8PCAiOlxuIjsKICAgICAgICBzb2x2ZSgpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=