405563: GYM101992 K Crazy queries

Given two strings S and P, and Q queries, for each query you are given a range [L, R].

For each pair of integers i and j chosen with uniform probability among all pairs where 1 ≤ i ≤ L and R ≤ j ≤ |S|, create a new string S₂ that is the result of concatenating S[1... i] and S[j... |S|]. You have to find the expected number of occurrences of P in S₂.

Note that all occurrences of P must be counted even if they overlap. The queries are independent meaning that the string S is the same for all queries.

The first line of the input contains a single integer T the number of test cases. Each test case starts with two lines. The first line contains string S and the second line contains P, where 2 ≤ |S| ≤ 10⁵ and 1 ≤ |P| ≤ 100. Each string consists of lowercase English letters.

The third line contains an integer Q, where 1 ≤ Q ≤ 5·10⁴. Each of the next Q lines represents a single query with two space-separated integers L and R, where 1 ≤ L < R ≤ |S|.

For each test case output Q lines. where each line contains the answer of the corresponding query in the form p/q where p and q are the numerator and denominator of the expected value in its simplest form respectively.

4
abaabaxbba
aba
4
2 7
1 5
6 9
4 5
abbaabxabba
aba
4
2 7
1 5
6 9
4 5
abbababbxaabaxabababxxa
abba
5
10 20
11 12
5 21
12 20
15 18
aaaaaaaaaa
aa
4
1 2
2 5
2 9
5 8

1/4
1/3
4/3
5/6
3/10
1/7
5/18
5/28
3/4
115/132
7/15
19/24
8/9
5/1
4/1
2/1
4/1