*Not an official ACM page*

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

#### 1994-1995 ACM International Collegiate Programming Contest

Western European Regional

Practice Session

# 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.
### Example Input

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.

This page maintained by
Ed Karrels.

Last updated November 11, 1997