Phép AND

Thành phố A nổi tiếng với nhiều danh lam thắng cảnh cũng như sự phát triển về công nghệ. Để duy trì sự phồn thịnh của thành phố, các công nhân cần làm việc vô cùng cật lực. Thành phố A hiện 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 là $i$.

Thành phố cần thực hiện $q$ công trình. Công trình thứ $j$ yêu cầu các công nhân có số thứ tự từ $L$ đến $R$ hợp lực xây dựng. Khi một nhóm công nhân cùng làm việc, chỉ số hiệu quả của nhóm 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.

Là một người cầu toàn, Quang muốn chỉ số hiệu quả là lớn nhất bằng cách loại bỏ không quá $k$ công nhân khỏi nhóm $L,L+1,\dots ,R$. Nhóm còn lại phải có ít nhất một công nhân (nếu nhóm chỉ còn một công nhân thì chỉ số hiệu quả bằng chỉ số xây dựng của công nhân đó). Các công trình được xét độc lập với nhau.

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.

Dữ liệu vào

• 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)$.

Dữ liệu ra

Gồm $q$ dòng, mỗi dòng chứa một số nguyên là chỉ số hiệu quả lớn nhất sau khi loại bỏ không quá $k$ công nhân trong công trình tương ứng.

Ràng buộc

• $1\le q\le {10}^4$.
• $1\le L\le R\le {10}^6$, $1\le k\le {10}^2$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $L,R,k\le {10}^2$.
• Subtask 2 ($80\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ