Description

  Consider the following algorithm:

1. Input n
2. Set Count to be 0
3. If n is equal to 1, then STOP
   Else Set 
4. Count = Count +1
5. GOTO Step 3.

Given one integer n. Please output the count after processing the algorithm.

For example:

If n = 22, then according to the algorithm. You will get 22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1. Thus the count for 22 is 15.

Input

The input contains several test cases and will end with EOF. In each test case, there is only one line contains an integer n.

For 9280: 1<=n<=1500

For 9281: 1<=n<=9000

For 9282: 1<=n<=100000

For 9283: 1<=n<=1000000

[Hint]

For 9280, the value during operation will not exceed 10^6. Time: 3s.

For 9281, the value during operation will not exceed 10^7. Time: 3s.

For 9282, the value during operation will not exceed 2^31. Time: 3s.

For 9283, the value during operation will not exceed 2^63. Time: 1s.

For 9283, and you may need to store the count of n that has already been calculated.

Please don't use cin/cout, or you will get TLE.

Output

 For each test case, output the count of n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please maintain a max-heap, which stores integers and is able to support following operations:

(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.

(2) POP – Delete the maximum element from the heap.

(3) TOP – Print the maximum element in the heap.

Input

There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 10000 at any time.

Output

For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S₁ and S₂. If the ASCII code of the first character of S₁ is smaller than the first character of S₂, we said that S₁ is smaller than S₂. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order.  If S₁ is S₂’s prefix, S₁ is smaller than S₂ and vice versa.

Input

There are multiple test cases.  Each case begins with an integer N (1 <= N <= 1000) in a line, and then N words follow, each word in a line.  The maximum length of words is 50.  The alphabets are 26 small English letters ‘a’ to ‘z’. The input is terminated if N = 0.

Output

For each test case, print the words in lexicographic order.    Print a blank line after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a fraction, find its simplest fraction representation. 

Input

 There many cases in the input. In each case, each line contains two integers a and b (a, b <= 100000), which represent the numerator and the denominator of a fraction. Input will be terminated by EOF.

Output

 For each case, output a line with the simplest fraction.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Alphametics, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter.

For example:
        S E N D
+     M O R E
------------------------------------------
= M O N E Y
The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, S = 9
- From Wikipedia

Now, we will give you the puzzle, you should calculate the puzzle’s minimum output. The detail you can find in the sample.

In this question, there are some limitations:
1. The leading digit should not be zero.
2. Each letter should represent different number.
3. If there are several possible output, you should print the minimum one.
4. Each input output length is less than or equal to 10.

Input

The first line will be an integer T(T<=40), which means the number of testcase.
Follow a blank line, there are T testcases.

Each testcase has three lines. The first and second line are the puzzle’s input, the third line is the puzzle’s output. Each length is less than or equal to 10. All the input character will between 'A' to 'Z'.

Every testcase is separated by a blank line.

Output

You should output the minimum output for that puzzle. The answer will quaranted fit in 32 bit number.

In the first sample, A=1,B=2 is the answer. A=2,B=4 is also ok, but we should output the minimum, so the answer is 2.

Sample Input  Download

Sample Output  Download

Tags

Discuss