每个测试点时限 1s 内存限制 256MB

背景

人类正面临着空前的危机,而你,是入侵的喵星人的走狗……

描述

2147483647年,喵星人占领了地球,并且妄图把人类关押在监狱里。为了防止人类串通反抗,每一个人都要关押在单独一个牢房里。可是在2147483647年,地球人实在是太多了(人数n<=10100),喵星人于是想出这样一个法子:

第一步:把地球人都丢到火星上去;

第二步:把地球切割成n块;

第三步:把地球人丢到切割的地球上去。

喵星人有一把巨大的刀叫“快刀”,一秒内可以用快刀切无数次地球,每次切割代价为1,使用快刀切割后形成的截面一定是一个平面,而切割后一秒之后被切割的两块才会分离。由于喵星人对此神刀的爱惜,它们会在一秒内切完地球。【就是说切完之前它都还是原样啦】

现在,喵星人想知道,它们切下地球要付出的代价至少是多少呢?由于喵星人没几根手指头,这个任务就交给走狗你了。

输入格式

一个整数n,含义见描述。

输出格式

一个整数,表示付出的最小代价。

样例输入1

4

样例输出1

2

样例输入2

8

样例输出2

3

数据范围与约定

  • 对于10%的数据:n<10
  • 对于30%的数据:n<103
  • 对于60%的数据:n<232
  • 对于100%的数据:n<10100

样例解释

在第一个样例中,只需要切两刀:即:如果把地球当作以原点为地心的空间直角坐标系,只需要垂直X轴来一刀,垂直Y轴来一刀。

在第二个样例中,只需要切三刀:即:如果把地球当作以原点为地心的空间直角坐标系,只需要垂直X轴来一刀,垂直Y轴来一刀,垂直Z轴来一刀。

【如果切出来的一块没有任何一个面属于原来地球的表面,那一块可以住人吗 ?可以。喵星人不需要给地球人人权的=。=】

来源

文化课