Professor Hasmot Ali loves to play string related problem. He assigns an easy lab task to his students. But they think it’s a hard problem. I know you are very smart. You can help his students to solve this problem. Given a string S, containing only lowercase English letters. There will be Q queries. Each line of query will contain two space separated strings, X and Y . For every query, your task is to calculate, how many distinct substrings of S which start with X and end with Y . [Substring definition: A substring is any contiguous portion of a string. A substring may be empty, or the entire string ] For Example: Given a string S = “abab”. There are total 8 distinct substrings. The list is below: [0] = “a” [1] = “ab” [2] = “aba” [3] = “abab” [4] = “b” [5] = “ba” [6] = “bab” [7] = “” There are 3 queries: 1stQuery:X=“a”andY =“a”. There are 2 distinct substring of S, satisfy the condition( [0] = “a” and [2] =“aba”). 2nd Query: X = “a” and Y =“b”. There are 2 distinct substring of S, satisfy the condition. ( [1] = “ab” and [3] = “abab” ). 3rd Query: X = “ba” and Y =“ab”. There is only one distinct substring satisfy the condition.([6] = “bab”). Input Input start with an integer T (≤ 3), denoting the number of test cases. Each case starts with a line containing string S (1 ≤ length(S) ≤ 1000). The next line contains an integer Q (1 ≤ Q ≤ 50000). Each of the next Q line contains two strings X (1 ≤ length(X) ≤ 10) and Y (1≤length(Y)≤10). Output For each query you have to print the number of distinct substring of S, which are start with X and end with Y .
2/2 Sample Input 1 abab 3 aa ab ba ab Sample Output Case 1: 2 2 1