Problem Description

The figure below is the well-known Pascal's Triangle:

If we list all numbers in order from top to bottom and from left to right, we get the following sequence:

$1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \ldots$

Given a positive integer $N$, output the position (which term) where $N$ first appears in the sequence.

Input Format

Input one integer $N$.

Output Format

Output one integer representing the answer.

6

13

Hint

For $20 \%$ of the test cases, $1 \leq N \leq 10$.

For all test cases, $1 \leq N \leq 10^9$.

Lanqiao Cup 2021, Round 1, Provincial Contest, Group B, Problem H.

Translated by ChatGPT 5