问题描述

下面的图形是著名的杨辉三角形：

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
 1 5 10 10 5 1
……    ……     ……

如果我们按照从上到下、从左到右的顺序把所有数排成一列，则可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1,$\cdots$。 给定一个正整数$N$， 请你输出数列中第一次出现$N$是在第几个数?

输入格式

输入一个整数$N$。

输出格式

输出一个整数代表答案。

样例输入输出

6

13

评测用例规模与规定

对于$20\%$的评测用例,$1 \leqslant N \leqslant 10$。

对于所有的评测用例，$1 \leqslant N \leqslant 1000000000$。

运行限制

• 最大运行时间：$1s$
• 最大运行内存：$256M$