One fine day, Benny decided to calculate the number of kilometers that she traveled by her bicycle. Therefore, she bought an odometer and installed it onto her bicycle. But the odometer was broken. It was not able to display the digit 3. This would precisely mean, that the odometer won't be able to display the numbers having one of their digits as 3.

For example, after the number \(1299\), the odometer will show \(1400\).

Benny was traveling a lot and now she wants to know the number of kilometers that she has traveled. You will be given only the number that Benny saw on the odometer. Your task is to determine the real distance.

Input format

The input consists of several test cases.
The first line contains one integer T denoting the number of test cases.
The next T lines contain a single integer N denoting the number that Benny saw on odometer.

Output format

For each test case, print the real distance in a single line.

Constraints

1 ≤ T ≤ \(10\)⁵
0 ≤ N < \(10\)⁹