Trò chơi được mô tả như sau: Hai người chơi luân phiên, mỗ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:

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

Kết quả:

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

Ràng buộc:

• ~1 \le T \lt 100; 1 \le X,Y,N \le 10^{9}~.

  Ví dụ:

Sample Input

2
1 2 1
3 2 3 

Sample Output

1
3