Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.

The maze type is shown in following figure:

S$###
$$#$$
$$$##
##$$F

it consists of S (starting point), #(walls), $(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S$###
$$#$$
$$$##
##$$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

Input

The first line has an integer N(1<=N<=1000), which means the number of test cases.

For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.

The following R lines, each containing C characters, specify the elements of the maze.

Output

Print out the least steps for each case, and there is a new line character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

S="ABCDEFG...XYZabcdefg...xyz"
Given two integers M and N, output all different possible sets of N characters from the first M characters in S. Print the sets in ASCII order(i.e. 'A'<'B'<'C'...<'Z'<'a'<'b'...<'z'). Each set should only be printed once, and the elements in the set should also be sorted in ASCII order.

For example, given M=3, N=2, you should output C(3,2)=3 lines, representing different sets of 2 characters from the set {A,B,C}(first 3 characters in S). The correct output is:
AB
AC
BC

Note that set {A,B} = {B,A}, thus should only be output once.

Input

The first line of input contains a positive integer T(T<=30), which indicates the number of test case. For the next T lines, each line contains two positive integers M, N (M^N<10^7, M>=N).

case1: 1<=M<=10, 1<=N<=2
case2: 1<=M<=26, 1<=N<=10
case3: 1<=M<=52, 1<=N<=10
case4: 1<=M<=52, 1<=N<=20

Output

For each test case, output all different possible sets of N characters from the first M characters in S. Each set a line, sorted in ASCII order.
Print a blank line after each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We can encrypt a string into other string.  One method is to put a string into an n×n array first, where n is the smallest number such that n^2 is equal to or larger than the length of the string.  Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order.  The encrypted string is the output of the row major order.  For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.

The output string is "Googrd  e  sed i".

If the end of the encrypted string are spaces, don't output them.  For example, the output of "Bass GG" is "B Ga Gss".

Input

The input consists of multiple lines. Each line is a test case, containing a string S. The number of test case is less than 100.

Case 1: the length of S is not more than 30.
Case 2: the length of S is not more than 100.
Case 3: the length of S is not more than 500.
Case 4: the length of S is not more than 1000.

Output

For each test case, output the encrypted string of S.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The words "waterproof" and "proofreading" have a common part "proof", which is the prefix of "proofreading" and the suffix of "waterproof". Given all possible pairs extracted from a list of words, your task is to find the length of the common suffix-prefix of a pair that is the longest one.

For example, if the list consists of "proofreading", "waterproof", and "ingredient", then the answer will be 5, since the common suffix-prefix for the pair of "waterproof" and "proofreading" contains 5 letters and is the longest, in comparison with the common suffix-prefix for the pair of "proofreading" and "ingredient", which is "ing" and has only 3 letters.

Input

There are multiple test cases (less than 500). Each case starts with an integer N indicating the number of words. The next N strings are the list of the words for this test case. Each word has at most M letters, all in lower-case.

case 1: 2 <= N <= 10, M=15
case 2: 2 <= N <= 20, M=15
case 3: 2 <= N <= 20, M=30
case 4: 2 <= N <= 30, M=30

Output

There should be one line after each test case. Each line shows an integer that represents the longest length of the common part for the best choice of word pair.

Sample Input  Download

Sample Output  Download

Tags

Discuss