Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
47 - ACM ICPC Regional 2005, Hangzhou - 1007
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