I I U P C   2 0 1 3

Problem A: See Emily Play

 

You are taking care of Emily this afternoon. To keep her entertained, you've designed a game for her involving some math. The rule for the game is such --

Emily is initially given a big number N. In each step she is supposed to:

 

  1. If N is 0, stop and call it a day
  2. If N is divisible by 2, divide N by 2.
  3. Otherwise, subtract 1 from N.

 

For example, starting with 14, she gets 7, 6, 3, 2, 1, 0

 

Now, you see, Emily is just a kid and hasn’t grown strong notions of rules yet. So, as you have given the rules to her, Emily tries, but misunderstands. In her mind, she rewrites the rules :

 

  1. If N is 0, stop and call it a day
  2. If N is divisible by 2, divide N by 2.
  3. Randomly and unbiasedly choose to do any of these two :
    • subtract 1 from N
    • add 1 with N

 

For each division Emily takes d seconds, For each subtraction she takes s seconds, for each addition she takes a seconds. Now that you know how she is bending the rules, you start to wonder how many seconds you have to see Emily play.

 

Input

First line of input will contain the number of test cases, T ≤ 100000. Then T test cases follow.  For each case there will be a single line containing four integers separated by space :

 

N d s a 

where ,

1 ≤ N ≤ 1000000

1 ≤ d, s, a ≤ 10

 

Output

For each case output a single line containing one real number, the expected number of seconds : T. Show exactly 3 digits after decimal point, properly rounded.

 

Sample Input

Output for Sample Input

6

1 1 1 1

2 1 1 1

3 1 1 1

4 1 1 1

5 1 1 1

1000000 1 1 1

 

3.000

4.000

5.500

5.000

6.750

29.367

 

 

Problem Setter : Pratyai Mazumder

Alternate Solution : Md. Mahbubul Hasan, Prasanjit Barua