Addition Simplification
Problem Statement

Bart Simpson is a student in the nursery school and is just learning how to add. The sum of multiple numbers needs to be calculated and the numbers can be either 1, 2 or 3 to make the calculation easier. Bart Simpson however, can calculate the sum only if the numbers to be added are in a non-decreasing order. For example Bart can calculate 1+1+2+2+3+3 but not 2+1+2+3+1+3. You have to help Bart to rearrange the numbers such that it is easy for him to calculate them.

Input Format

First line contains an integer 't' denoting total test cases.

Next 't' lines contain non-empty string s - the sum Bart needs to calculate. String doesn’t contain spaces and contains only digits and the '+' character.

Length of string s <=100. t<=100. Output Format

For each test case, the new order displayed in the format such that Bart can count followed by a new line.

Sample Input

4
1
2+2
3+2+1
2+2+1+1+3
Sample Output

1
2+2
1+2+3
1+1+2+2+3

Explanation

For the above cases, output is displayed in the format such that Bart can calculate it.

Play Auditions
Problem Statement

There are a total of ‘a’ men and ‘b’ women who would be coming to a play audition. In order to select participants for the play we need to follow the given constraints. While choosing the group, there should be exactly ‘x’ people in total and should contain more than 3 men and at least 1 woman. You are required to find total number of ways in which the group can be formed. The groups are considered distinct only if the composition of participants differ.

Input Format

A single line contains three space separated integers a, b, x.

Constraints:

4 ≤ a ≤ 30 1 ≤ b ≤ 30
5 ≤ x ≤ a + b

Output Format

Ouput the integer denoting the required possible number of ways.

Sample Input

5 2 5

Sample Output

10

Crypto-Codes
Problem Statement

Alice maintains a set consisting of ‘a’ numbers which he finds to be very lucky. He is developing a secure system for which he needs to generate a crypto-code. Now, he has some constraints while generating the crypto-code. Let S be a set of all possible numbers generated by the concatenations of ‘b’ positive numbers chosen from Alice’s set of lucky numbers. The crypto-code C is the largest number from the resultant set S such that the value of C modulo 9 should be zero.

Help Alice find out the Crypto-Code C.

Input Format

First line contains an integer T- denoting the total number of test cases.
For each test case, the following lines follow:
One line contains two integers ‘a’ and ‘b’.
Following ‘a’ lines contain the ‘a’ lucky numbers.

Constraints

T<=30
1 <= b <= a <= 100
1 <= all lucky numbers <= 1000000

Output Format

Output a single integer denoting the answer to the corresponding test case. If an answer is not possible, print -1.

Sample Input

2
3 2
1
2
3
5 2
1
2
3
4
5

Sample Output

-1
54

Explanation

For the first case, there in no number in the set S whose value mod 9 is 0. For the second case, 54 formed by the concatenation of 5 and 4 is the largest number satisfying the given conditions.

Game of Blocks
Problem Statement

Tyrion Lannister is trapped in a rectangular room when he is imprisoned by Lysa Arryn. This room consists of blocks coloured either yellow or red. Tyrion Lannister is standing on a red block. He can move to one of the four adjacent blocks from the block on which he is standing. But he cannot move on yellow blocks and can only move on the red blocks.

Write a program which will count the number of red blocks which Tyrion can reach by repeating the moves described above.

Input Format

First line consists of two positive integers A and B; A and B are the numbers of blocks in the x- and y- directions respectively. (2 <= A,B <=20)

The next B lines each contains A chars. Each character represents the colour of a block as follows:

'.' - a red block
'#' - a yellow block
'@' - Tyrion on a red block (appears exactly once)
The end of the input is indicated by a line consisting of two space separated zeroes.
Total cases in one test file <=200.

Output Format

Output the total number of red blocks Tyrion can reach from the start block (including start block).

Sample Input

2 3
..
.@
.#
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output

5
13

Explanation

In the first case, Tyrion can first go up, then left, then below and then further below so as to reach 5 red blocks including the one on which he is currently standing.

Number Game
Problem Statement

You are given two numbers ‘a’ and ‘b’. Your task is to make the two numbers equal by performing the minimum number of operations. In one operation, you can pick any one of the number and divide it by 2 if it is divisible by 2 or you can divide it by 3 if it is divisible by 3 or you can divide it by 5 if it is divisible by 5.

Input Format

The first line contains the total number of test cases 't'.
Next 't' lines contain 2 space separated integers 'a' and 'b'.

Constraints

1 <= a,b <= 1000000000 t<=100 Output Format

Output a single integer on a new line denoting the minimum number of operations for each test case. If it is not possible to make the numbers equal, print -1.

Sample Input

3
7 8
13 13
20 15

Sample Output

-1
0
3

Explanation

For the first case, the numbers cannot be made equal, hence -1. For the second case, they are already equal hence 0. For the third case, 20 can be divided by 2 two times and 15 divided by 3 for 1 time thus taking a minimum of 3 operations.

Character Pairs
Problem Statement

There is a string M of length L. You have to find the total number of pairs satisfying the conditions:
0 <= a,b < L and M[a]=M[b] where 'a' and 'b' are integers.

Input Format

First line contains total test cases denoted by integer 't'.
Next t lines contain the string M.

Constraints

t<=10.
1<=L<=100000.
String can contain lower-case letters and numeric characters.

Output Format

On a new line, a single integer denoting the answer to the test case.

NOTE
Pairs (p,q) and (q,p) are considered distinct.

Sample Input

2 djsce20 hh

Sample Output

7
4

Explanation

For the second case, Note that 'a' can be equal to 'b' thus giving 4 distinct pairs.

Poor Dishes
Problem Statement

In a restaurant, we have 'x' dishes numbered from 1 to x. Each dish can either be attributed as a poor tasting dish or a pleasant tasting dish. You definitely want to stay clear of the poor tasting dish. You find various reviews online that tell you the number of poor dishes within an inclusive range of dishes. You find 'y' such reviews. You need to find out the minimum number of ‘poor dishes’ and the maximum number of 'poor dishes' present in the menu depending upon the 'y' reviews that you obtain. We are finding out the minimum and maximum numbers of poor dishes as we cannot exactly determine the number of poor dishes.

Input Format

First line conatins 2 spaced integers 'x' and 'y'.
The next 'y' lines contains 3 spaced integers 'p' 'q' 'r' indicating that there are exactly 'r' poor dishes in the range of [p, q] dishes.

Constraints

0 <= x,y <= 101
1 <= p <= q <= x
0 <= r <= q-p
The given information will be sufficient to find the minimum and maximum poor dishes.

Output Format

Print 2 space separated integers denoting the minimum no. of poor dishes and the maximum number of poor dishes in the entire menu respectively.

Sample Input

3 2
1 2 1
2 3 1

Sample Output

1 2

Explanation

The initial line is "3 2", i.e. that there are 3 dishes and we have 2 sets of reviews. The next line says there is one poor dish in the set of dishes {1, 2}. The final line says there is one poor dish in the set {2,3}. There are two possibilities for this scenario: Dishes number 1 and 3 are poor or dishe number 2 is poor.