A. Khepri and the Counting Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nour, also known as Khepri, is obsessed with numbers and mathematics. He always manages to find qualitative solutions to such problems. That's why his friend Abdelaleem attempted to challenge him with a problem and dared him to find the expected result within 3 minutes. As Abdelaleem expected, Nour was able to solve it and find the expected result within just one minute (thanks to his typing speed on the keyboard as well).

The problem was that Abdelaleem would give him a number $$$n$$$, and he wanted to count how many positive numbers smaller than or equal to $$$n$$$ consisted of an odd number of digits.

Can you solve this problem in a short time and beat Nour's record (just one minute)?

Input

The first line contains an integer $$$T$$$ – the number of test cases.

For each test case:

The first and the only line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

Output

For each test case, output on a single line the number of positive integers less than or equal to $$$n$$$ that consisted of an odd number of digits.

Example
Input
3
9
999
9999999
Output
9
909
9090909