#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
#define eb emplace_back
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define fi first
#define se second
#define pqueue priority_queue
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

template<typename T1, typename T2>
ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << '(' << p.fi << ", " << p.se << ')'; }

template<typename T>
void printv(const T& v) { for(auto i : v) cerr << i << ' '; cerr << '\n'; }

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;

//All indexing is 0-based
using namespace __gnu_pbds;
template<class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar

template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

//Returns no. of values x for which ceil(n / x) == y (y must be > 1).
inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }

//Returns no. of values x for which floor(n / x) == y
inline ll FF(ll n, ll y) { return n / y - n / (y+1); }

//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }

#define N 1000005
#define int ll
// #define trace(...) 42

//Link: https://c...content-available-to-author-only...s.com/string/suffix-automaton.html

string s; int n; 

struct state {
    int len, link; //len: Length of longest string ending at the state
                   //link: suffix link
    bool terminal; //Is the state terminal ?
    map<char, int> next;
};

state st[N << 1];
int cnt, last;

void init(int cur) {
    st[cur].len = 0;
    st[cur].link = -1;
    st[cur].terminal = 0;
    st[cur].next.clear();
}

void sa_init() {
    cnt = 0;
    //source node is at index 0.
    // st[0].len = 0, st[0].link = -1;
    // st[0].terminal = 0;
    // st[0].next.clear();
    init(0);
    last = 0;
    cnt++;
}

void sa_extend(char c) {
    int cur = cnt++;
    init(cur);
    st[cur].len = st[last].len + 1;
    int p = last;
    while(p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if(p == -1) {
        st[cur].link = 0;
    }
    else {
        int q = st[p].next[c];
        if(st[q].len == st[p].len + 1) {
            st[cur].link = q;
        }
        else {
            int clone = cnt++;
            st[clone].terminal = 0;
            st[clone].len = st[p].len + 1;
            st[clone].link = st[q].link;
            st[clone].next = st[q].next;
            st[cur].link = st[q].link = clone;
            while(p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
        }
    }
    last = cur;
}

void find_terminals() {
    int p = last;
    while(p) {
        st[p].terminal = 1;
        p = st[p].link;
    }
}

//O(N lg K), where K is the size of the alphabet
void SuffixAutomaton() {
    sa_init();
    n = s.size();
    for(int i = 0; i < n; i++) {
        sa_extend(s[i]);
    }
    find_terminals();
}

void printSA() {
    for(int i = 0; i < cnt; i++) {
        cout << "i: " << i << '\n';
        cout << "Terminal: " << st[i].terminal << '\n';
        cout << "Transitions:\n"; 
        for(auto p : st[i].next) {
            cout << p.first << " -> " << p.second << '\n';
        }
        cout << "Suf Link: " << st[i].link << '\n';
        cout << '\n';
    }
}

int tot[N], pret[N];
int ans[N], pre[N];
bool vis[N];

void dfs(int cur) {
    vis[cur] = 1;
    if(cur) {
        int l, r;
        l = st[st[cur].link].len + 1;
        r = st[cur].len;
        ans[l]++, ans[r+1]--;
        // trace(l, r);
    }
    for(auto p : st[cur].next) {
        int i = p.se;
        if(!vis[i]) dfs(i);
    }
}

int norm(int x) {
    if(x < 0) x += mod;
    if(x >= mod) x -= mod;
    return x;
}

void prep() {
    SuffixAutomaton();
    fill_n(ans, n + 5, 0);
    fill_n(vis, cnt, 0);
    dfs(0);

    for(int i = 1; i <= n; i++)
        ans[i] += ans[i-1];

    for(int i = 0; i <= n; i++) {
        // trace(i, ans[i]);
        pre[i] = ans[i];
        if(i) pre[i] = add(pre[i], pre[i-1]);
    }
    assert(!pre[0]);
}

main()
{   
    #ifdef CP
        freopen("/home/tarun/Desktop/input.txt", "r", stdin);
     // freopen("/home/tarun/Desktop/output.txt", "w", stdout);
    #endif
    sync;
    clock_t clk = clock();
    cerr << "I will return...\n";

    rep(i, 0, N) {
        if(i == 0) tot[i] = pre[i] = 1;
        else {
            tot[i] = mul(26, tot[i-1]);
            pret[i] = add(pret[i-1], tot[i]);
        }
    }

    int oo = 1;
    tests(t) {
        // trace(t);
        cout << "Case " << oo++ << ":\n";
        cin >> s; n = s.size();
        prep();
        int q; cin >> q;
        while(q--) {
            int l, r; cin >> l >> r;
            --l;
            int ans = pret[r];
            ans = sub(ans, pret[l]);
            ans = sub(ans, sub(pre[r], pre[l]));
            // trace(sub(pre[r], pre[l]));
            cout << ans << '\n';
        }
    }

    cerr << "...don't you ever hang your head.\n";
    cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';
}

//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment