Math Test#11713
Sign in

Math Test

1 second
256 megabytes
Easy

Sakurako is in the fifth grade and has a Math test tomorrow. He decides to prepare for the test and get the maximum score. The topic he is currently studying is the absolute value of numbers.

The absolute value of , denoted by , is defined as:

|a| = \begin{cases} a & \text{if } a \geq 0, \\ -a & \text{if } a < 0. \end{cases}

It isn't a difficult topic, and Sakurako easily solved almost all the exercises. However, there is one task he finds challenging. The problem statement is as follows:

“Given integers , , and . What is the value of if you replace it with |x-y| exactly times?”

Sakurako feels this task is too general and asks you to provide answers for some cases so he can look for a pattern to solve it himself. Please help Sakurako with his preparation for the Math test.

Input

The first line contains an integer (1 \le q \le 10^5) — the number of cases Sakurako asks about.

Each of the following lines contains three integers , , and (0 \le x \le 10^9; 1 \le y \le 10^9; 0 \le k \le 10^9) — the values for each test case.

Output

For each case, output a single integer — the value of after replacements.

Examples

Example

Loading
Loading

Note

In the third case, we have x = 12, y = 5, k = 3. So we perform three replacements:

  1. x := |x-y| = |12-5| = 7;

  2. x := |x-y| = |7-5| = 2;

  3. x := |x-y| = |2-5| = 3.

Hence, the answer for that case is .

Scoring

  1. (11 points): \sum k \le 10^5;

  2. (27 points): x \le y for all cases;

  3. (21 points): is divisible by for all cases;

  4. (41 points): without additional restrictions.