# XY Sequence solution codeforces

You are given four integers 𝑛n, 𝐵B, 𝑥x and 𝑦y. You should build a sequence 𝑎0,𝑎1,𝑎2,…,𝑎𝑛a0,a1,a2,…,an where 𝑎0=0a0=0 and for each 𝑖≥1i≥1 you can choose:

• either 𝑎𝑖=𝑎𝑖−1+𝑥ai=ai−1+x
• or 𝑎𝑖=𝑎𝑖−1−𝑦ai=ai−1−y.

Your goal is to build such a sequence 𝑎a that 𝑎𝑖≤𝐵ai≤B for all 𝑖i and ∑𝑖=0𝑛𝑎𝑖∑i=0nai is maximum possible.

Input

The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) — the number of test cases. Next 𝑡t cases follow.

The first and only line of each test  case contains four integers 𝑛n, 𝐵B, 𝑥x and 𝑦y (1≤𝑛≤2⋅1051≤n≤2⋅105; 1≤𝐵,𝑥,𝑦≤1091≤B,x,y≤109).

It’s guaranteed that the total sum of 𝑛n doesn’t exceed 2⋅1052⋅105.

## XY Sequence solution codeforces

Output

For each test case, print one integer — the maximum possible ∑𝑖=0𝑛𝑎𝑖∑i=0nai.

Example

input

Copy

```3

5 100 1 30

7 1000000000 1000000000 1000000000

4 1 7 3```

## output XY Sequence solution codeforces

```15

4000000000

-10```

Note

In the first test case, the optimal sequence 𝑎a is [0,1,2,3,4,5][0,1,2,3,4,5].

In the second test case, the optimal sequence 𝑎a is [0,109,0,109,0,109,0,109][0,109,0,109,0,109,0,109].

In the third test case, the optimal sequence 𝑎a is [0,−3,−6,1,−2][0,−3,−6,1,−2].