You are given a string S consisting of lowercase English letters denoting different types of candies. A substring of a string S is a string S' that occurs in S. For example, "bam" is a substring of "babammm". Each candy costs 1 unit. You can pick some continuous candies such that you can create a palindrome of length K by using some or all picked candies. Your task is to find the minimum cost to create a palindrome of length K.
Input Format:
First line contains string S.
Next line contains an integer T denoting the number of test cases.
Next T lines contain a single integer K.
Output Format:
For each test case, print minimum cost as mentioned above. If you cannot create a palindrome of length K then, simply print -1.
Constraints:
1≤|S|≤1051≤T≤101≤K≤105
Test Case 1: You can pick candies denoted by "mm" and create a palindrome of size 2. So the cost will be 2 units.
Test Case 2: You can pick candies denoted by "babam" and rearrange them, "bamab", to create a palindrome of size 5. So the cost will be 5 units.
