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 104 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.
## Input
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 104 characters).Note: the number of unknown letters in one spell’s name won’t exceed 10.
## Output
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.
[samples]
**Definitions**
Let $ \text{MOD} = 1013 $.
Let $ c \in \mathbb{Z} $ be the given magical code, $ 0 \leq c < \text{MOD} $.
Let $ s \in \{a,\dots,z,?\}^* $ be the spell name string of length $ n \leq 10^4 $, with at most 10 occurrences of `'?'`.
Define the hash function $ H: \{a,\dots,z\}^* \to \mathbb{Z}_{\text{MOD}} $ as:
$$
H(s) = \left( \sum_{i=0}^{n-1} s_i \cdot 31^{n-1-i} \right) \mod \text{MOD}
$$
where $ s_i \in \{a,\dots,z\} $, and each letter is interpreted as its ASCII value (i.e., `'a' = 97, ..., 'z' = 122 $).
Let $ Q \subseteq \{0, \dots, n-1\} $ be the set of indices where $ s_i = '?' $, with $ |Q| \leq 10 $.
**Constraints**
1. $ 1 \leq T \leq 20 $
2. $ 0 \leq c < 1013 $
3. $ |s| \leq 10^4 $, and $ |Q| \leq 10 $
4. Each `'?'` must be replaced by a character in $ \{a,\dots,z\} $ (ASCII 97 to 122).
**Objective**
Count the number of assignments $ f: Q \to \{97, \dots, 122\} $ such that:
$$
H(s_f) = c
$$
where $ s_f $ is the string obtained by replacing each $ '?' $ at index $ i \in Q $ with $ f(i) $.
If the count is exactly 1, output the unique spell name $ s_f $.
Otherwise, output the count.