Server Time: Fri Nov 17, 2017 8:50 pm
Welcome ( logout
1314 - Names for Babies
  PDF (English) Statistics Forum
Time Limit: 4 second(s) Memory Limit: 32 MB

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 Input

Output for Sample Input

1

abcdef

2 5

Case 1: 14

Note

This problem was used in contest 12. But the length of S was between 2 and 100.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan