D. Spell Generation
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Hiding various taboo words in a string to achieve the effect of a spell is a common phenomenon in the magical world. To better cope with cases of illegal spell usage, the people of this country need to learn spellcraft to help themselves defend against spells.

Today's lesson is about a simple spell generator, which has two modes: Click and Press.

For each click, it takes $$$1$$$ second to generate a spell of length $$$1$$$.

For each press, you must first choose a positive integer $$$x$$$, and then it takes $$$2^x$$$ seconds to generate a spell of length $$$10^x$$$.

Now you are given some lengths of spells that need to be generated, and you need to calculate the minimum time required to generate each spell.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 50000$$$), representing the total number of requests.

Each of the following lines contains an integer $$$r$$$ ($$$1\le r \le 10^{18}$$$), representing the length of each spell to be generated.

Output

Output $$$T$$$ lines, each line representing the minimum time required.

Example
Input
5
23
61
62
114514
1919810
Output
7
13
14
106
474