## 文理学院程序设计在线练习

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 18   Accepted Submission(s): 9
Problem Description

Mr.Bluefly is a local tyrant who is planning to buy a new “Bigger than bigger” as the iphone6+ is coming out. And in the same time, it is a good chance for him to say goodbye to his old cellphone number from the Telecom company. Why? There is an old saying that: “Once you choose Telecom, you don’t have to worry about upgrading your cellphone(because there’s no choice at all)”. However, he finds it difficult to choose a number from so many available numbers. He prefers numbers in “ababab” style sequence but can’t make up his mind. So he decides to let someone make a number selector program and select a number randomly. So here is the question: One needs to know the amount of numbers that less-than n and in “ababab” style sequence to make this selector. Will you help him with it?

Input

An integer T in the first line, then follows T groups of test data.
Each data group is an integer n in one line.
(0<=T<=100,0<=n<=1000000000000000000)

Output

Each line an integer of the amount of valid numbers of each test data group. See sample.

Sample Input
3
10
111
89999
Sample Output
10
92
325
Source

2014市赛