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 S₁ and S₂ are both valid, then S₁S₂ 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

Lagrange's four-square theorem says that any natural number can be represented as the sum of four integer squares.
Here are some examples:
3 = 1*1 + 1*1 + 1*1 +0*0
5 = 2*2 + 1*1 + 0*0 + 0*0
14 = 3*3 + 2*2 + 1*1 + 0*0
Note that there may be more than one representation. For example, 21 can be represented in the following two ways:
21 = 3*3 + 2*2 + 2*2 + 2*2
21 = 4*4 + 2*2 + 1*1 + 0*0

Our task:
Among all of the four-square representations of a given natural number N, find the largest sum of the four integers. In the case of N=21, the answer is 9 because 3+2+2+2 is greater than 4+2+1+0.

Input

The first line contains an integer T that indicates the number of test cases. (1<=T<=40)
The next T lines are the T test cases.
Each test case provides an integer N (0<=N<=50000) for deriving the four-square representations.

Case 1: 0<=N<=200.
Case 2: 0<=N<=1000.
Case 3: 0<=N<=10000.
Case 4: 0<=N<=50000.

Output

For each test case, output the answer in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two sets of numbers, output their intersection set.

Input

There are multiple test cases.

Each case contains four lines.

The first line begins with an integer N.

The second line contains N integers, representing the numbers in the first set.

The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set.

All the numbers are 32 bit signed integers. All the numbers in the set are listed in ascending order and are unique.

The input is terminated if N = 0.

For Case 1, 1 <= N, M <= 10³
For Case 2, 1 <= N, M <= 10⁴
For Case 3, 1 <= N, M <= 10⁵
For Case 4, 1 <= N, M <= 10⁶

Output

For each test case, print the intersection of the two sets. Output each number in ascending order and separate them by a space. If the intersection of the two sets is an empty set, print "empty" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

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