提示: 欢迎访问OurACM平台。
Problem 1390 Infinite String

Accept: 256    Submit: 399
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Consider the following infinite string:

144449999999991616161616161616161616161616161625...

If you could not discover the pattern yet, the following is the description of how the string is created:

Start with an empty string s.
Append all the digits of 12 (i.e. 1) at the end of s 12 (i.e. 1) times.
Append all the digits of 22 (i.e. 4) at the end of s 22 (i.e. 4) times.
Append all the digits of 32 (i.e. 9) at the end of s 32 (i.e. 9) times.
Append all the digits of 42 (i.e. 16) at the end of s 42 (i.e. 16) times.
...

Given an integer n, what is the nth character of the above infinite string?

Input

The input file contains at most 200 lines of inputs. Each line contains an integer n (0 < n < 10^9). Input is terminated by a line containing a single zero. This line should not be processed.

Output

For each input n, print the nth character of the infinite string in a single line.

Sample Input

1 2 3 4 5 6 100000 1000000 10000000 999999999 0

Sample Output

1 4 4 4 4 9 3 8 6 9

Source

2005 HKUST Local Contest

Submit  Back  Status  Discuss