• # For Solution

Chef is playing badminton today. The service rules of this singles game of badminton are as follows:

1. The player who starts the game serves from the right side of their court.
2. Whenever a player wins a point, they serve next.
3. If the server has won an even number of points during a game, then they will serve from the right side of the service court for the subsequent point.

Chef will be the player who begins the game.

Given the number of points PP obtained by Chef at the end of the game, please determine how many times Chef served from the right side of the court.

Please see the sample cases below for explained examples.

### Input Format Badminton Serves solution codechef

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• Each test case consists of a single line containing one integer PP, the points obtained by Chef.

### Output Format

For each test case, output in a single line the number of times Chef served from the right side of the court.

• 1T1031≤T≤103
• 0P1090≤P≤109

### Badminton Serves solution codechef Sample Input 1

4
2
9
53
746


### Sample Output 1

2
5
27
374


### Explanation Badminton Serves solution codechef

Test case 11: Chef obtained 22 points at the end of the game. This means he served two times from the right side of the court, once when his score was 00 and once again when his score was 22.

Test case 22: Chef obtained 99 points at the end of the game. This means he served 55 times from the right side of the court. The points when he had to serve from right were: 0,2,4,6,80,2,4,6,8.