Thành phố có vô hạn công nhân được đánh số từ ~1~. Công nhân thứ ~i~ có chỉ số xây dựng bằng ~i~.

Thành phố cần thực hiện ~q~ công trình. Với mỗi công trình, tất cả công nhân có chỉ số từ ~L~ đến ~R~ được huy động. Chỉ số hiệu quả của một nhóm công nhân bằng kết quả phép AND theo bit của chỉ số xây dựng của tất cả công nhân trong nhóm.

Quang được phép loại bỏ không quá ~k~ công nhân trước khi thực hiện công trình.

Yêu cầu: Với mỗi công trình, hãy xác định chỉ số hiệu quả lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên dương ~q~ ~(1 \le q \le 10^4)~;

• Mỗi dòng trong ~q~ dòng tiếp theo chứa ba số nguyên dương ~L,R,k~ ~(1 \le L \le R \le 10^6;\ 1 \le k \le 10^2)~.

Output

Gồm ~q~ dòng. Mỗi dòng chứa chỉ số hiệu quả lớn nhất sau khi loại bỏ không quá ~k~ công nhân trong truy vấn tương ứng.

Scoring

Sample Input 1

2
1 3 1
4 8 1

Sample Output 1

2
4