Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

B-Number

Limits 1s, 512 MB

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 <= T <= 20000). Each of next T lines contain an integer B (1<= B <= 231) 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

InputOutput
1
6
3
InputOutput
2
9
102
4
35

For the first sample, Dollar’s notebook looked like this:

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


    Discussion
    Statistics

    100% Solution Ratio

    fsshakkhorEarliest, 6M ago

    kzvd4729Fastest, 0.0s

    fsshakkhorLightest, 131 kB

    fahmid07Shortest, 41B

    Submit

    Login to submit