## Bytelandian gold coins

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n
can be exchanged in a bank into three coins: n/2, n/3 and n/4.
But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange
rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars
you can get for it?

### Input

The input will contain several test cases (not more than 10). Each
testcase is a single line with a number n, 0 <= n <= 1 000 000 000.
It is the number written on your coin.

### Output

For each test case output a single line, containing the maximum amount
of American dollars you can make.

### Example

Input:

Output:

You can change 12 into 6, 4 and 3, and then change these into
\$6+\$4+\$3 = \$13.

If you try changing the coin 2 into 3 smaller coins, you will get
1, 0 and 0, and later you can get no more than \$1 out of them.
It is better just to change the 2 coin directly into \$2.

 Time Limit: 9 sec Source Limit: 50000 Bytes

## Lucky lucky number

Every great chef knows that lucky numbers are positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Our chef has recently returned from the Lucky country. He observed that every restaurant in the Lucky country had a lucky number as its name. He believes that having a lucky number as a restaurant name can indeed turn out to be very lucky.

Every great chef knows that lucky numbers are positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Our chef has recently returned from the Lucky country. He observed that every restaurant in the Lucky country had a lucky number as its name. He believes that having a lucky number as a restaurant name can indeed turn out to be very lucky.

Our chef believes that it is possible to make a lucky number having N digits even luckier. Any number following the rules below is called Lucky lucky number —

1. The number contains only digits 4 and 7.
2. Count of digit 4 in the number should be divisible by 7.
3. Count of digit 7 in the number should be divisible by 4.

Help our chef to compute the count of digit 4 in the smallest Lucky lucky number having N digits.

### Input

First line contains T, number of test cases. Each of the next T lines contains a number N, the number of digits in the Lucky lucky number to be formed.

1<=T<=1000
1<=N<=1000000000 (10^9)

### Output

If it is not possible to form a Lucky lucky number having N digits, output -1. Otherwise, output the count of digit 4 in the smallest Lucky lucky number having N digits.

### Example

Input:

Output:

Explanation
For the last test case, N = 15, the smallest lucky lucky number is
444444477777777. The count of digit 4 is 7.

 Time Limit: 1 sec Source Limit: 50000 Bytes

## Holes in the text

Chef wrote some text on a piece of paper and now he wants to know how many holes are in the text. What is a hole? If you think of the paper as the plane and a letter as a curve on the plane, then each letter divides the plane into regions. For example letters «A», «D», «O», «P», «R» divide the plane into two regions so we say these letters each have one hole. Similarly, letter «B» has two holes and letters such as «C», «E», «F», «K» have no holes. We say that the number of holes in the text is equal to the total number of holes in the letters of the text. Help Chef to determine how many holes are in the text.

### Input

The first line contains a single integer T <= 40, the number of test cases. T test cases follow. The only line of each test case contains a non-empty text composed only of uppercase letters of English alphabet. The length of the text is less then 100. There are no any spaces in the input.

### Output

For each test case, output a single line containing the number of holes in the corresponding text.

### Example

Input:

Output:

 Time Limit: 1 sec Source Limit: 50000 Bytes

## Hotel Bytelandia

A holiday weekend is coming up, and Hotel Bytelandia needs to find out if it has enough rooms to accommodate all potential guests. A number of guests have made reservations. Each reservation consists of an arrival time, and a departure time. The hotel management has hired you to calculate the maximum number of guests that will be at the hotel simultaneously. Note that if one guest arrives at the same time another leaves, they are never considered to be at the hotel simultaneously (see the second example).

### Input

Input will begin with an integer T, the number of test cases. Each test case begins with an integer N, the number of guests. Two lines follow, each with exactly N positive integers. The i-th integer of the first line is the arrival time of the i-th guest, and the i-th integer of the second line is the departure time of the i-th guest (which will be strictly greater than the arrival time).

### Output

For each test case, print the maximum number of guests that are simultaneously at the hotel.

### Constraints

• T≤100
• N≤100
• All arrival/departure times will be between 1 and 1000, inclusive

 Time Limit: 1 sec Source Limit: 50000 Bytes

## Problem 1

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the number is 1245,it will become 5421 .Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

### Input

The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

### Output

For each case, print exactly one line containing only one integer — the reversed sum of two reversed numbers. Omit any leading zeros in the output.

### Example

Input:
1
24 1

Output:
34
Читать далее Problem 1