//height[i]=suffix（sa[i-1]）和suffix（sa[i]）的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀
    void calheight（int *r,int *sa,int n） {
    int i,j,k=0;
    for（i=1; i<=n; i++）
    rank1[sa[i]]=i;
    for（i=0; i<n; height[rank1[i++]]=k）
    for（k k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++）；
    }
    int solve（int n） {
    int i,sum=0;
    for（i=1; i<=n; i++） {
    sum += n - sa[i] - height[i] ;
    }
    return sum;
    }
    /****以上模版****/
    char now[2005] ;
    char str[N];
    inline void RD（int &ret） {
    char c;
    do {
    c = getchar（）；
    } while（c < '0' || c > '9'） ;
    ret = c - '0';
    while（（c=getchar（）） >= '0' && c <= '9'）
    ret = ret * 10 + （ c - '0' ）；
    }
    inline void OT（int a） {
    if（a >= 10）OT（a / 10） ;
    putchar（a % 10 + '0'） ;
    }
    struct QU {
    int s ,e ,id ;
    } QQ[10005] ;
    bool cmp（QU a ,QU b） {
    if（a.s == b.s）return a.e < b.e ;
    return a.s < b.s ;
    }
    int ans[11111] ;
    int main（） {
    int i,n,t;
    scanf（"%d",&t）；
    while（t--） {
    scanf（"%s",str）；
    memset（ans , 0 , sizeof（ans））；
    int xd ;
    cin 》 xd ;
    for （int i = 0 ; i < xd ; i ++ ） {
    RD（QQ[i].s） ;
    RD（QQ[i].e） ;
    QQ[i].s -- ;
    QQ[i].e -- ;
    QQ[i].id = i ;
    }
    sort（QQ , QQ + xd , cmp） ;
    int st = QQ[0].s ;
    int ed = QQ[0].e ;
    int num = 0 ;
    for （int i = st ; i <= ed ; i ++ ）r[num ++] = （int）str[i] ;
    r[num] = 0 ;
    dc3（r , sa ,num + 1 , 200） ;
    calheight（r , sa, num ） ;
    ans[QQ[0].id] = solve（num） ;
    for （int i = 1 ; i < xd ; i ++ ） {
    if（QQ[i].s != QQ[i - 1].s） {
    num = 0 ;
    for （int j = QQ[i].s ; j <= QQ[i].e ; j ++ ）r[num ++] = （int）str[j] ;
    r[num] = 0 ;
    dc3（r , sa , num + 1 ,200 ） ;
    calheight（r ,sa ,num） ;
    ans[QQ[i].id] = solve（num） ;
    ed = QQ[i].e ;
    } else {
    if（QQ[i].e == QQ[i - 1].e） {
    ans[QQ[i].id] = ans[QQ[i - 1].id] ;
    } else {
    for （int j = ed + 1 ; j <= QQ[i].e ; j ++）r[num ++] = （int）str[j] ;
    r[num] = 0 ;
    dc3（r ,sa ,num + 1 , 200） ;
    calheight（r ,sa ,num） ;
    ans[QQ[i].id] = solve（num） ;
    ed = QQ[i].e ;
    }
    }
    }
    for （int i = 0 ; i < xd ; i ++ ） {
    OT（ans[i]） ;
    puts（""） ;
    }
    }
    return 0;
    }