Time Limit: 1000 mSec Memory Limit : 32768 KB

Consider the following infinite string:

Start with an empty string s.

Append all the digits of 1^{2} (i.e. 1) at the end of s 1^{2} (i.e. 1) times.

Append all the digits of 2^{2} (i.e. 4) at the end of s 2^{2} (i.e. 4) times.

Append all the digits of 3^{2} (i.e. 9) at the end of s 3^{2} (i.e. 9) times.

Append all the digits of 4^{2} (i.e. 16) at the end of s 4^{2} (i.e. 16) times.

...

Given an integer n, what is the nth character of the above 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 1

Append all the digits of 2

Append all the digits of 3

Append all the digits of 4

...

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

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.

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

1
2
3
4
5
6
100000
1000000
10000000
999999999
0

1
4
4
4
4
9
3
8
6
9