Not an official ACM page
[1994 Western European Regional problem set | My ACM problem archive | my home page]

# Problem H

## Ulam

One of the most famous problems in number theory is Ulam's conjecture (but it is known under many other names as well). Ulam's conjecture states that if you start with any natural number, and at each step divide it by 2 (if even) or multiply it by 3 and add 1 (if odd), you will get to 1 eventually.

To test this hypothesis, we have written a flashy program, but somehow have forgotten to include an essential part: a function which takes any natural number and returns the result of applying one step of the above procedure.

Would you be so kind to do that for us?

### Input Specification

The first line of input consists of a single integer N, specifying the number of test cases. Then follow N lines, each containing a single positive integer N to which the above procedure should be applied. In all cases N will not exceed 1,000,000,000.

### Output Specification

For each test case you should print one line of output. If the input equals one, print '```No next number.```'. In all other cases print '`After P we get Q.`', where P is the input number and Q is the result of dividing by 2 or multiplying by 3 plus 1.

```5
1000
301
17
10
1
```

### Example Output

```After 1000 we get 500.
After 301 we get 904.
After 17 we get 52.
After 10 we get 5.
No next number.
```