401485: GYM100482 E Magical Code

Do you know how magicians cast spells? The spell consists of its name and its magical code. The casting is done by saying its name while keeping in mind the magical code (only then the spell works). Only the most experienced, the smartest and the most talented magicians can create they own spells. They name their spell and determine its purpose. They make some rituals near the Tree of Power. And if the magician is worth the tree creates the magical code for this spell.

However, the tree itself is designed and created by the mathematician who told me the mechanism of creating spells. Here is the algorithm in “our language”:

const int MOD = 1013;

int code = 0;

for (int i = 0; i < spell_name.size(); i++)

    code = (code * 31 + spell_name[i]) % MOD;

printf("You are worth it! Your power is unleashed by the number %d" , code);

The creator of the tree wants to boost your knowledge. So he tells some of the most recent codes and parts of the spell’s name. You need to tell what the maximum number of spells could have this magical code. If there is only one choice - print it!

Note: the spell’s name consists only of lowercase English alphabet letters (’a’-’z’).

The first line contains the number of test cases T (T ≤ 20). The first line of each test case contains the magical code, c (0 ≤ c < MOD). The second line of each test case constains the spell’s name (unknown letters are given as ’?’) (the name is no longer than 10⁴ characters).

Note: the number of unknown letters in one spell’s name won’t exceed 10.

For each test case output one line containing “Case #tc: answer”, where tc is the number of the test case (starting from 1). If there is one possible answer - print the name of the spell as the “answer”, otherwise, print the number of ways.

2
31
fo?bar
31
f???ar

Case #1: foobar
Case #2: 16