Background

张三是一名勇士，他被村民选为代表去屠杀恶龙。传说中这条恶龙无恶不作，每年的七月半都会从山谷中飞出，到村子里屠杀无辜的百姓。为了守护村庄，为了不辜负村民们的信任，张三踏上了屠龙之路。他每天苦练剑法，终于熟练掌握住了屠龙秘籍。这年七月，张三与恶龙殊死搏斗，终于杀死了恶龙。虚弱的恶龙竟然在死后现出了原型，原来恶龙竟然是个美女，张三落泪T^T，可是美女的胸前已经被张三狠狠戳了个洞洞了，是救不活了。美女恶龙奄奄一息地从屁股底下掏出一块银锭，对张三说：“勇士，这是你通关的奖励，只要你能把这块价值为$v$的银锭分成最少的$n$块，使得这$n$块银锭能够买下任意价值在 1~$v$中的物品，你就可以开启异世界的大门。”可惜张三的数学一向不好，你能告诉他最少要把银锭分成几块吗？

Description

比如$v$等于7 时我们可以切成 1,2,4

这时有:

1=1;

2=2;

3=1+2;

4=4;

5=1+4;

6=2+4;

7=1+2+4; 此时$n$=3;

Format

Input

一个整数$v$,$v\le 1,000,000,000$;

Output

输出一个整数代表符合要求的最小$n$;

Samples

7

3

Limitation

1s, 1024KiB for each test case.