题目描述

让我们将无限连续整数按顺序写在一行（不包含任何空格），并将它们的平方写在第二行。这样会生成两个不同的长数字，现在我们需要求这两个数字的和。前30位的计算结果如下所示：
结果的第1位是$2$，第2位是$7$，第3位是$2$，依此类推。给定一个整数$k$，你需要输出结果数字的第$k$位。

输入格式

输入文件包含多个测试用例。每个测试用例占一行，包含一个整数$k$（$0 < k \leq 2^{31} - 1$）。

输入以一行单独的$0$结束，该行无需处理。

输出格式

对于每个测试用例，输出一行，表示结果数字的第$k$位。

输入样例 1

2  
5  
30  
0  

输出样例 1

7  
1  
8  

题目来源

POJ Monthly--2005.07.31, Islamic Azad University of Mashhad – Collegiate Coding Challenge 1