Do bão lũ nên An và Bình phải ở nhà. Vì quá chán nên An và Bình đã nghĩ ra trò chơi với những con số như sau:

An và Bình, mỗi người sẽ chọn một số nguyên dương bất kỳ (gọi con số An chọn là \(X\) và con số Bình chọn là \(Y\)). Có tổng cộng \(N\) lượt chơi và An là người chơi trước. Ở mỗi lượt chơi thì người chơi sẽ gấp đôi con số mình đã chọn lên (tức là \(X=2\times X\) hoặc \(Y=2\times Y\)).

Yêu cầu: Sau \(N\) lượt chơi, gọi \(G = \left[ \frac{\max(X, Y)}{\min(X, Y)} \right]\). Hãy tìm giá trị \(G\).

Input

• Dòng đầu tiên chứa \(Q\) - số lượng câu hỏi cần trả lời \((Q \le 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(X, Y, N\) \((X, Y, N \le 10^{12})\) - lần lượt là con số ban đầu mà An chọn, Bình chọn và số lượt chơi.

Output

• Ứng với mỗi câu hỏi in ra giá trị \(G\) thỏa mãn yêu cầu đề bài.

Example

2
1 1 2
1 2 3

1
1

Note

• Ở truy vấn thứ nhất:
  • Lượt 1: An gấp đôi số của mình lên \((1 \times 2 = 2)\);
  • Lượt 2: Bình gấp đôi số của mình lên \((1 \times 2 = 2)\);
  • Sau hai lượt chơi, giá trị \(G=1\).
• \([\alpha]\) là phần nguyên của giá trị thực \(\alpha\)

Scoring

• Subtask 1 \((20\%)\): \(Q \le 100\), \(X, Y, N \le 10^4\)
• Subtask 2 \((80\%)\): Không ràng buộc gì thêm.