Given a number, print out the length of the shortest addition chain for that number.
An addition chain is an ascending sequence of integers starting with 1, where each integer can be expressed as a sum of any two (not necessarily distinct) previous integers. An addition chain for n contains n. Here are some addition chains:
Note: One of (1,2,4)'s children is intentionally omitted.
Each line of input will contain a single integer n, less than 300.
Output, alone on a line, the length of the shortest addition chain for n.