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ố này, 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 tại có vô hạn số công nhân, các công nhân được đánh số từ \(1\) đến \(+\infty\). Công nhân thứ \(i\) có chỉ số xây dựng là \(i\). Hiện tại thành phố cần thực hiện \(q\) công trình, mỗi công trình yêu cầu các công nhân từ \(l\) đến \(r\) hợp lực để xây dựng. Được biết, khi \(n\) công nhân cùng làm chung với nhau thì chỉ số hiệu quả của họ sẽ là tổng phép and chỉ số xây dựng của \(n\) công nhân. Là một người cầu toàn, SHIBA muốn chỉ số hiệu quả là lớn nhất bằng cách loại bỏ ra không quá \(k\) công nhân. Đây là công việc vô cùng khó khăn, vì thế bạn hãy giúp SHIBA hoàn thành nhé.

Lưu ý:

• nếu không có công nhân nào xây dựng thì chỉ số hiệu quả được tính bằng \(0\).
• bạn có thể tham khảo về phép AND tại đây https://en.wikipedia.org/wiki/Bitwise_operation#AND

Input:

• Dòng thứ nhất chứa \(1\) số nguyên dương \(q\) (\(1 \le q \le 10^4\)).
• \(q\) dòng tiếp theo mỗi dòng chứa \(3\) 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 in ra chỉ số hiệu quả lớn nhất sau khi loại bỏ ra không quá \(k\) công nhân.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le l,r,k,q \le 10^2\)
• Subtask \(2\) (\(80\%\) số điểm): \(1 \le l,r \le 10^6, 1 \le k \le 10^2,1 \le q \le 10^4\)

Example

2
1 3 1
4 8 1

2
4