Mr. Ed is a very sophisticated man and likes art very much, that is why he and his pals are visiting the amazing museums of Paris. His favourite museum is the Musée d’Chaîne; it has a huge art collection, but the masterpiece of the exhibition is a world famous string of n characters. Mr. Ed has spent hours and hours looking for exquisite pairs of substrings inside the masterpiece. A substring of a string S = s1s2...sn, represented as Ti,j for a pair of indexes i ≤ j, is described as the concatenation sisi+1 . . . sj−1sj of characters from string S. Two substrings of S are considered distinct if their indexes i and j are not the same. The group does not want to observe a single string all day long. In order to leave the museum as soon as possible, you want to help Mr. Ed counting every pair of distinct substrings of the exhibition string that are exquisite. If you don’t have as much artistic taste as Mr. Ed, a pair of strings is considered exquisite if they share a common prefix of at least k characters. If you don’t have idea what a prefix is sigh, we define it as a substring with starting index i equal to 1. Input The first line of input contains a positive integer T representing the number of test cases. The following T lines contain a non-empty string of 1 ≤ n ≤ 105 lowercase letters of the English alphabet representing the museum exhibition string, followed by an integer number 1 ≤ k ≤ n; the length of the minimum prefix required in an exquisite pair of strings. Output For each test case in the input, print a single line with an integer representing the number of exquisite substring pairs, modulo 1,000,000,007 (109 + 7). See format below for details. Sample Input 5 aaaa 3 ababab 4 cdabcdab 5 qwertyuiop 2 abcabcabcabcx 5 Sample Output Case #1: 3 Case #2: 7 Case #3: 10 Case #4: 120 Case #5: 313