题目描述

首先给出两个短串 A=’4567’ (4 个字符 ) ， B=’123’(3 个字符 ) 。反复进行如下的操作得到一个长串 C 。 （１） C=B+A ( 例如： A=’4567’ ,B=’123’ C=B+A=’1234567’) （２） A=B B=C ( 上述例子 A=’123’ B=’1234567’) 请你编程找出这个长串的第 n 个字符。

输入格式

第一行包含一个整数n (1<=n<=10^9^)

输出格式

仅一行，包含一个字符，表示这个长串的第 n 个字符。

样例

输入

9

输出

2

来源

字符串