题目描述

Ivan 放学回家后，想了很久今天数学小组课上老师讲的无限数列。作为例子之一，老师给出了如下有趣的正整数序列：

老师解释说，在这个序列中，每一个正整数都会出现无限多次。不过 Ivan 还对另一个问题感兴趣：怎样确定序列中第 $n$ 个位置上的数是多少？老师回答说这很简单，并让 Ivan 自己思考这个问题。

Ivan 不仅喜欢数学，也喜欢编程，因此他想实现一个算法，能够在非常大的 $n$ 的范围内快速回答这个问题。请帮助他。

输入格式

第一行输入一个整数 $n$。

输出格式

输出一个整数，表示给定序列的第 $n$ 项。输出不得包含空格和前导零。

样例

输入

7

输出

3

说明

评测方不保证存在一种解法可以在所有测试上以两倍时间余量运行。

评分方式

本题共有若干组测试。每组分数只有在通过该组所有测试以及所有前置测试组后才会获得。比赛期间可以看到所有测试的评测结果。