Problem A. ABC ≡

Statement

Given an empty string.

You can add to that string characters 'A', 'B' and 'C'.

• For each character 'A' at position i you get S_a + f(i) points, f(i) - number of characters 'A' before position i.
• For each character 'B' at position i you get S_b − g(i) points, g(i) - number of characters 'B' before position i.
• For each character 'C' you get S_c points.

Your should calculate maximum score you can get with a string of length N.

Input format

First line contains an integer T - number of tests.

Each test contains four integers: N, S_a, S_b and S_c.

Output format

For each test print one integer - maximum score.

Constraints

1 ≤ T ≤ 10⁴

1 ≤ N, S_a, S_b, S_c ≤ 10⁹

Sample tests

3
3 2 7 1
4 6 1 3
5 3 1 6

18
30
30