Trò chơi được mô tả như sau: Hai người chơi luân phiên, mỗi người được nhận một con số tương ứng là X và Y. Có N vòng chơi. Người có số X chơi trước. Tại mỗi vòng chơi, người chơi nhân gấp đôi con số của mình lên. Kết thúc vòng chơi, giả sử người có số X bây giờ có số W, người có số Y bây giờ có số Z. Bạn hãy cho biết thương nguyên của phép chia giữa max(W, Z) và min(W, Z).

Dữ liệu vào

• Dòng đầu tiên của đầu vào chứa số nguyên T cho biết bộ số dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số 3 số nguyên X, Y, N.

Kết quả

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa một số nguyên là kết quả tương ứng.

Ràng buộc

~ 1 \leq T \leq 10^2; 1 \leq X, Y, N \leq 10^9~

Ví dụ:

INPUT

   2
   1 2 1
   3 2 3

OUTPUT

   1
   3