Addition chains

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.

Input specification:

Each line of input will contain a single integer n, less than 300.

Output specification:

Output, alone on a line, the length of the shortest addition chain for n.

Sample input:


1
2
3
5
8
13

Sample output:


1
2
3
4
4
6