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

There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S1and S2. If the ASCII code of the first character of S1 is smaller than the first character of S2, we said that S1 is smaller than S2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order.  If S1 is S2’s prefix, S1 is smaller than S2 and vice versa.

Hint: Because of large input size, please use scanf and printf for efficiency.

Input

There are multiple test cases.  Each case begins with an integer N (1 <= N <= 1000) in a line, and then N words follow, each word in a line.  The maximum length of words is 50.  The alphabets are 26 small English letters ‘a’ to ‘z’. The input is terminated if N = 0.

Output

For each test case, print the words in lexicographic order.    Print a blank line after each case.

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).

Case 1 : N≤50

Case 2 : N≤100

Case 3 : N≤1000

Case 4 : N≤10000

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

Compute how many carries will occur when calculating the sum of two decimal numbers A and B.

Input

For each case a line, there are two positive integers A and B. There are multiple cases (<1000) terminated by EOF.

Case #1: 0<A, B<1000

Case #2: 0<A, B<10^6

Case #3: 0<A, B<10^12

Case #4: 0<A, B<10^1000

Output

For each case a line, output how many carries occur.

Sample Input  Download

Sample Output  Download

Tags

Discuss