# [SOLUTION] A. Treasure Chest SOLUTION CODEFORCES

A. Treasure Chest SOLUTION CODEFORCES
time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Monocarp has found a treasure map. The map represents the treasure location as an OX axis. Monocarp is at 00, the treasure chest is at x, the key to the chest is at y.

Obviously, Monocarp wants to open the chest. He can perform the following actions:

• go 11 to the left or 11 to the right (spending 11 second);
• pick the key or the chest up if he is in the same point as that object (spending 00 seconds);
• put the chest down in his current point (spending 00 seconds);
• open the chest if he’s in the same point as the chest and has picked the key up (spending 00 seconds).

Monocarp can carry the chest, but the chest is pretty heavy. He knows that he can carry it for at most k seconds in total (putting it down and picking it back up doesn’t reset his stamina).

What’s the smallest time required for Monocarp to open the chest?

Input

The first line contains a single integer t (1t1001≤�≤100) — the number of testcases.

The only line of each testcase contains three integers x,y�,� and k (1x,y1001≤�,�≤100xy�≠�0k1000≤�≤100) — the initial point of the chest, the point where the key is located, and the maximum time Monocarp can carry the chest for.

Output

For each testcase, print a single integer — the smallest time required for Monocarp to open the chest.

Example
input

Copy
3
5 7 2
10 5 0
5 8 2
output

Copy
7
10
9

Note

In the first testcase, Monocarp can open the chest in 77 seconds with the following sequence of moves:

• go 55 times to the right (55 seconds);
• pick up the chest (00 seconds);
• go 22 times to the right (22 seconds);
• pick up the key (00 seconds);
• put the chest down (00 seconds);
• open the chest (00 seconds).

He only carries the chest for 22 seconds, which he has the stamina for.

In the second testcase, Monocarp can pick up the key on his way to the chest.

In the third testcase, Monocarp can’t use the strategy from the first testcase because he would have to carry the chest for 33 seconds, while he only has the stamina for 22 seconds. Thus, he carries the chest to 77, puts it down, moves 11 to the right to pick up the key and returns 11 left to open the chest.

SOLUTION

# Function to calculate the smallest time required to open the chest
def smallest_time_to_open_chest(x, y, k):
if k >= x:
return x + y
else:
return (k + (k * (x // k))) + (x % k) + y

# Read the number of test cases
t = int(input())

# Iterate through each test case
for _ in range(t):
x, y, k = map(int, input().split())
result = smallest_time_to_open_chest(x, y, k)
print(result)