Math Test

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

The absolute value of $a$, denoted by $|a|$, is defined as: $|a|=\{\begin{array}{ll}a& \text{if }a\ge 0,\\ -a& \text{if }a<0.\end{array}$

It isn't a difficult topic, and Sakurako easily solved almost all the tasks. However, there is a task with which he has difficulties. The statement is the following:

"Given integers $x,y,k$. What is the value of $x$ if you replace it with $|x-y|$ exactly $k$ times?"

Sakurako thinks this problem is too generalized and asks you to give him the answer for some cases so that he can find the solution on his own. Please help Sakurako with the preparation for the Math test.

Input

The first line contains an integer $q(1\le q\le 10^5)$ — the number of cases Sakurako has given to you.

Each of the following $q$ lines contains three integers $x,y,k(0\le x\le 10^9;1\le y\le 10^9;0\le k\le 10^9)$ — Sakurako asks you to solve the task for this triple of integers.

Output

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

Examples

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 $3$.

Scoring

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

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

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

4. ($41$ points): without additional restrictions.