숫자 이어 붙이기

시간 제한 메모리 제한
1 Sec 128 MB

문제 설명

상진이는 숫자 공부를 위해 자연수를 A4용지에 하나 둘 적기 시작 했습니다.

12345678910111213141516171819202122.....

연속으로 적다보니 10번째에 오는 숫자는 1 이고 17번째에 오는 숫자는 3이라는 사실을 발견 했습니다.
1000번째에 오는 숫자가 무엇인지 계속 적어보았는데 집에있는 종이가 바닥이나 어머니에게 혼이 났습니다.

이런 상진이를 도와 P번째에 오는 숫자가 무엇인지 계산하는 프로그램을 작성 해 주세요.

입력

첫 줄에 테스트 케이스 T (1 <= T <= 1,000) 가 주어집니다.

두 번째 줄 부터 T줄에 거쳐 찾아야하는 위치 P (1 <= P <= 2,147,483,647) 가 주어집니다.

출력

각 테스트 케이스당 한줄에 하나씩 P번째에 오는 숫자가 무엇인지 계산하는 프로그램을 작성 해 주세요.

입력 예시

3
10
17
2147483647

출력 예시

1
3
2