Long time ago, there was a strange kingdom. Peoples of different religions, different cultures used to live there. But as they were different, their names were also different. So, in schools, offices, it was quite tough to call someone using his/her name, because some names were too hard to be pronounced by persons from different culture.
So, the king made a plan. He took a string S and two integers p and q and made a rule that names of the babies should be a substring of S, and the length should be between p and q (inclusive).
Now you are given S, p and q you have to find the number of distinct names that can be made.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing a string S. The length of S will be between 2 and 10000 (inclusive) and S contains lowercase English letters only. The next line contains two integer p and q (1 ≤ p ≤ q ≤ length(S)).
Output
For each case, print the case number and the number of distinct names that can be made.
Sample
Sample Input | Sample Output |
---|---|
1 abcdef 2 5 | Case 1: 14 |