B-Number

Bruce Lee has recently become the sensei (Master) of the very institute which taught him everything. He has found out a way to be unique to his students. After every class of him starts, he says “I am back.” Also, before leaving the class, he says, “I will be back.” Dollar, a naughty but brilliant student of Master Lee, has decided to make a notebook of his class which will only consist of these two lines. So, after a semester, his notebook look something like this.

I will be back.
I am back.
I will be back.
I am back.
I will be back.
.......................
.......................
I am back.

You saw Dollar's notebook after the semester ended and wondered how many classes of Lee did Dollar attend in the whole semester. When you asked Dollar, he said you need not count the times he wrote these two sentences. He count the number of times the letter "b" appears in his notebook and wrote it infront of the notebook. He named it the B-number and said you can guess the number of classes attended by having a look at it. Can you really guess how many classes of Master Lee did he attend in that semester? Dollar told you three important things: (i) Master Lee did not say "I am back." in his first class (ii) he did not say "I will be back" in his last class. (iii) He attended at least two classes in a semester.

Input

The first line of input contains an integer $T$ ($1 \le T \le 20000$). Each of next $T$ lines contain an integer $B$ ($1 \le B \le 2^{31}$) which denotes a B-number. Each line is separated with a newline.

Output

For each B (B-number) in input, print in separate lines how many classes Dollar attended to write this number. Each line will have a newline.

Samples

Input	Output
1 6	3
For the first sample, Dollar's notebook looked like this: I will be back. I am back. I will be back. I am back.

Input	Output
2 9 102	4 35