Migrated from Lutece 1473 Bob and Alice are playing palindrome

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bob and his girl friend Alice like palindromes very much.

One day,Bob writes string on a paper.Alice is very excited.So she wants to know can she divide the string into k non-empty palindromes.

Bob is very busy.So can you help him?

Input

First line is a positive integer T , represents there are T test cases.

For each test case:

First line contains one string consisting of n lowercase English letters(1<=n<=100000)

Second line contains a number Q(1<=Q<=10),the questions Alice wants to ask.

Following Q lines,each lines contains a number k(1<=k<=n),that means Alice wants to know can she divide the string into k non-empty palindromes.

If she can do it,you should output "yes".

If she can't do it,you should output "no".

Output

For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case.

Samples

2
aba
3
1
2
3
aaa
3
1
2
3

Case #1:
yes
no
yes
Case #2:
yes
yes
yes

Resources

“玲珑杯”ACM比赛 Round #2