Problem Description

Given two non-negative integers $n$ and $m$, you need to determine the value of the non-negative integer $n$ after applying the following operation exactly $k$ times:

• $n \gets n \operatorname{and} \max(n - m, 0)$.

Input Format

There are $T$ test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

• A single line contains three non-negative integers $n, m, k$.

Output Format

For each test case, output a single line containing one non-negative integer — the answer.

7
1 2 2
3 5 1
2 3 3
6 7 1
1 6 1
4 9 1
9 1 1

0
0
0
0
0
0
8

Hint

For $100\%$ of the data:

• $1 \le T \le 2 \times 10^5$;
• $0 \le n, m, k \le 2^{30}$;
• $k \ge 1$.