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² 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 contains severel test cases. Each test case consists of two lines. The first line contains a positive number n, and the second line contains a string S. The string S should be encrypted by a n*n array. The number of test case is less than 100.

Case 1: the length of S is not more than 16.
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 a single line containing the encrypted string.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

S="ABCDEFG...XYZabcdefg...xyz"
Given two intergers 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 charcters from the set {A,B,C}(first 3 charaters 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 interger 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

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

The first line is an integer T (T <= 100) denoting the number of test cases. 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

The output should contain T lines for the T cases. 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

Description

Given an article, calculate the value of each character and output them in the descending order of their values. The price of characters is calculated as follows: 1 dollar for a letter ‘a’, 2 dollars for a letter ‘b’ … and 26 dollars for a letter ‘z’. 'A' and 'a' are not the same in this problem, uppercase letters are considered to be much more valuable than lowercase letters. If a lowercase letter costs X dollars, then the uppercase letter of it should cost X^2 dollars. For example, we know that 'c' costs 3 dollars, then 'C' should cost 9 dollars.
Please count the total value of lowercase and uppercase letters in the article, can you help us with that?

Input

There are multiple articles in the input. In each test case, the first line contains one integer, N, which indicates the number of lines in the article.

Note that each line may contains up to 10^7 characters.

Case 1
0 < N <=10
Case 2
0 < N <=50
Case 3
0 < N <=100
Case 4
0 < N <=1000

Output

Output the total value of each character in the descending order. Do not print the character not in the article. If two characters have the same value, output the one with smaller ASCII code first.

Print a blank line after the output of each test 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 ≤ 1000) 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 ~ Case 3 would not contain any empty line.

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss