E. Waymo orzorzorz
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jason wants to orz Waymo! To achieve this, he can use the following operations:

1. Type "orz" in $$$A$$$ seconds.

2. Copy all the text in $$$B$$$ seconds.

3. Paste all the copied text in $$$C$$$ seconds.

Since Jason is in a hurry, please help him minimize the amount of time he spends to orz Waymo at least $$$N$$$ times.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of test cases.

Each test case contains one line, with four positive integers $$$A$$$, $$$B$$$, $$$C$$$, and $$$N$$$ ($$$1 \le A,B,C \le 10^6, 1 \le N \le 10^9$$$).

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy $$$N \le 2000$$$.

Tests $$$3-6$$$ satisfy $$$N \le 5 \cdot 10^5$$$.

Tests $$$7-12$$$ satisfy $$$N \le 10^7$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each test case, output a single integer — the minimum amount of time to type "orz" at least $$$N$$$ times.

Example
Input
4
1 1 1 20
1 2 3 143
1 4 3 890
3 20 7 650
Output
9
29
51
156
Note

In the test case of the sample test, it is optimal to type orz 3 times, then copy, paste, copy, paste, paste, paste.

—

Problem Idea: jay_jayjay

Problem Preparation: jay_jayjay

Occurrences: Novice K, Advanced E