Special Calculator

Given a positive integer \( n \) initially displayed on a calculator screen, you are also given three non-negative integers \( a \), \( b \), and \( c \) representing how many times buttons A, B, and C will be pressed respectively. The calculator works as follows:

• When button A is pressed, the number on the screen becomes \( \lfloor n/2 \rfloor \).
• When button B is pressed, the number becomes \( \lfloor (n+1)/2 \rfloor \).
• When button C is pressed, if \( n>0 \) then the number becomes \( \lfloor (n-1)/2 \rfloor \); if \( n=0 \), it remains 0.

You must press button A exactly \( a \) times, button B exactly \( b \) times, and button C exactly \( c \) times. You may press these buttons in any order. Determine the minimum possible number that can be obtained on the screen after performing all these operations.

inputFormat

The first line contains an integer ( T ) ((1 \le T \le 1000)), the number of test cases. Each of the following ( T ) lines contains four integers ( n ), ( a ), ( b ), and ( c ) (where ( 0 \le n \le 10^9 ) and ( 0 \le a,b,c \le 1000)).

outputFormat

For each test case, output a single line with the minimum possible number after performing the given operations in an optimal order.

sample

3
114 1 1 1
191 1 1 1
1 0 1 0

14
24
1