Nhân ngày quốc tế thiếu nhi, ami đã tặng em gái của Flow God xấu-trai-hơn-ami một chiếc máy thần kì. Trên chiếc máy là 2 nút màu tím và hồng, cùng 2 số \(H\) và \(I\). Nếu ấn nút màu tím, số \(H\) sẽ tăng 1 đơn vị, nếu ấn nút màu hồng, số \(I\) sẽ tăng 1 đơn vị. Flow God ghen tuông vì ami đã tặng cho em gái cưng của mình một món quà cool ngầu như thế, bèn tìm ra cách để ami phải mất mặt.

Flow God xấu-trai-hơn-ami muốn ami ấn các nút tím và hồng tổng cộng không quá F lần. Sau khi thực hiện các thao tác, giả sử 2 số mà ami nhận được là \(N\) và \(R\), Flow God muốn \(gcd(N,R)\) là lớn nhất có thể. Nhắc lại, \(gcd(a,b)\) là một số \(c\) lớn nhất mà cả \(a\) và \(b\) đều chia hết cho \(c\) (quy ước \(gcd(0, n)=gcd(n, 0)=n\) với mọi số nguyên dương \(n\)). Tuy nhiên, ami quá thần thánh, đã tìm ra kết quả siêu nhanh. Flow God tức tối, giận cuom1999 chém ma. "ma" ở đây chính là các bạn tham gia contest.

Các bạn cần trả lời \(q\) câu hỏi của Flow God, mỗi câu hỏi có dạng \(H\) \(I\) \(F\). Cần in ra \(gcd(N,R)\) lớn nhất, \(N\) và \(R\) là các số nhận được, sau khi ấn hai nút tím và hồng không quá \(F\) lần.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q\) là số câu hỏi của Flow God xấu-trai-hơn-ami.
• Tiếp theo là \(q\) dòng, mỗi dòng chứa một bộ số nguyên không âm \(H\) \(I\) \(F\) là một câu hỏi.

Output

• In ra \(q\) dòng, mỗi dòng là một số nguyên là \(gcd(N,R)\) lớn nhất có thể đạt được.

Dữ liệu đảm bảo luôn có kết quả.

Constraints

• \(H, I \leq 10^5\)
• \(q \leq 10^2\)
• \(F \leq 10^{13}\)

Scoring

• Subtask \(1\) (\(5\%\) số điểm): \(H = 0, I \leq 10^5, F \leq 10^{13}, q \leq 10^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{5}\).
• Subtask \(3\) (\(10\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F = 0\)
• Subtask \(4\) (\(65\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{13}\)

Example

3
0 1 1
1 1 2
2 4 1

2
2
2