Generator

Time Limit: 2 Seconds
Memory Limit: 32768 KB

### THE 30th ACM/ICPC ASIA REGIONAL 2005 HANGZHOU SITE

#### Onsite Contest Session

## Problem G: Generator

We can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as a specific pattern occurs in the random string.

Your task is to predict the expected length of the generated string.

**Input Description**

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

Each test case consists of a single integer N (1 <= N <= 26) which is the number of letters used, and a pattern, which is a non-empty string consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 12.

**Output Description**

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each test case, print the expected length of the generated random string.

**Sample Input**

5
2 A
2 ABA
3 AAAAA
26 ACMICPC
26 ZJUZJU

**Sample Output**

Case 1:
2
Case 2:
10
Case 3:
363
Case 4:
8031810176
Case 5:
308933352

Submit
Status