Description

Please find the frequency of the most frequent alphabetical character (ignore case) in the given string.

Input

There will be multiple test cases,
each test case contains a line of string with length N (N<=10000)
There will be no more than 10000 test cases.
Test cases will terminate by an EOF.

Output

For each test cases,
output a line with a number representing the frequency.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order.  Each node has unique integer identification (ID), but all IDs may not be consecutive.

Input

There are multiple test cases.  Each test case begins with an integer N, denoting the number of relations in the tree.  In the following N lines, each line contains two integers a and b, which means node a is node b’s parent.   After that, the next line contains an integer R, which represents the root of the tree.  You can assume that all the nodes will be on the same tree.  The input is terminated by N = 0.

Case 1: 1 <= N <=10 , 1 <= a,b <= 20

Case 2: 1 <= N <=100 , 1 <= a,b <= 200

Case 3: 1 <= N <=1000 , 1 <= a,b <= 2000

Case 4: 1 <= N <=1000 , 1 <= a,b <= 2000000

Output

For each test case, print the pre-order of the tree.  In each level, traverse the node with smaller ID first.

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

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

Given a string S, find all different possible set of K characters in the string, and output them in dictionary order. Representation of each set in the ouput should be in alphabetical order.

For example, in the case that K=2 and the given string S is "CDBABBD", the output will be

AB
AC
AD
BB
BC
BD
CD
DD

Notice that the set {'D', 'B'} is equivalent to {'B', 'D'}.  

The string "BD" in output stands for the set {'D', 'B'} or {'B', 'D'} equivalently.

Input

The first line of input is a positive integer T (T <= 30), which indicates the number of test cases.

For each test case, there are a non-empty string S and a positive integer K seperated by a space in a line. The length of S is less than or equal to 100 and S contains only upper-case letter 'A'-'K'; The number K is less than or equal to min{10, |S|}.

For dataset 1: T≤10, K≤3, |S|≤10
For dataset 2: T≤15, K≤5, |S|≤25
For dataset 3: T≤20, K≤8, |S|≤50
For dataset 4: T≤30, K≤10, |S|≤100

Output

For each test case, find all different possible set of K characters in the string, and output them in dictionary order. Output one set per line, and the representation of each set should be in alphabetical order.

Print a blank line after each test case.

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