Alex Book :
Difficulty Level : Easy
Submissions : 73
Asked In :
Marks :10
: 0 | : 0
Alex has a book of an Infinite number of pages. Imagine practically when a book is opened $$$2$$$ pages get opened $$$1$$$ on left and $$$1$$$ on the right side except starting page which doesn't have any page to its left. In an open book left and right page numbers which open together form a spread. $$$1^{st}$$$ page doesn't have any page to its left so page number 1itself forms a spread and further all spreads have $$$2$$$-page numbers in them. The first spread contains page $$$1$$$, the second spread contains pages $$$2$$$ and $$$3$$$, the third spread contains pages $$$4$$$ and $$$5$$$ and the fourth spread contains pages $$$6$$$ and $$$7$$$ and so on.
Your task is to determine the first page number of the very first spread where the sum of digits of the page numbers is $$$S$$$. If no such spread exists, print $$$-1$$$.
Note: Page number $$$1$$$ itself forms a spread and thus is the first page for the first spread.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first and only line of each testcase contains an integer $$$S$$$ $$$(1 \le S \le 10^5)$$$. It is guaranteed that the sum of $$$S$$$ over all the testcases does not exceed $$$10^5$$$.
For each test case, print the answer to the problem in a single line.
3194
1 4 -1
In sample test case 2,
- The first spread contains page $$$1$$$ only, the sum of digits of page number is $$$1$$$.
- The second spread contains pages $$$2$$$ and $$$3$$$, the sum of digits of page numbers is $$$5(2+3)$$$.
- The third spread contains pages $$$4$$$ and $$$5$$$, the sum of digits of page numbers is $$$9(4+5)$$$.
