Nick qualified to Hackerrank Semifinal so Elene decided to gift him a box of sweet. But she won't just give it away without a twist!

Elene gave Nick boxes numbered from to . He knows that only one box is full of sweets and others are empty. Nick can ask Elene some questions in order to find out which box is full of sweets.

In each question, Nick will chose two integers and ().

Let be index of the box with sweets.

    if Elene will tell him "BU" and he will have to pay her ByteDollars.
    if Elene will tell him "BUT" and he will have to pay her ByteDollars.
    if Elene will tell him "BUTA" and he will have to pay her ByteDollars.

You have to calculate the minimum number of ByteDollars that Nick will need to spend in order to find the box full of sweets.

Input Format

First line contains , number of tests.
Next line contains four integers: , , and .

Constraints




Output Format

For each test print minimum amount of money, Nick will need.

Sample Input

3
10 1 2 3
15 5 5 5
15 2 2 3

Sample Output

5
15
7

Explanation

In test1 Nick will need 5 Bytedolars.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score