MEX (số nhỏ nhất không có) của một dãy là số nguyên không âm nhỏ nhất không có trong dãy. Ví dụ:

+ MEX của \(\lbrack 2,2,1\rbrack\) là 0, bởi 0 không có trong dãy.

+ MEX của \(\lbrack 3,1,0,1\rbrack\) là 2, bởi 0 và 1 thuộc dãy, nhưng 2 thì không.

+ MEX của [0, 3, 1, 2] là 4 bởi 0, 1, 2 và 3 thuộc dãy, nhưng 4 thì không.

Tìm số MEX lớn nhất của một dãy các số nguyên không âm sao cho phép OR bit của tất cả các phần tử trong dãy không vượt quá \(X\).

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên \(t\ (1 \leq t \leq 10^{5})\) cho biết số test.

+ \(t\) dòng tiếp theo, mỗi dòng ghi một số nguyên \(x\ (0 < x < 10^{9})\).

Kết quả:

+ Với mỗi test in ra một dòng chứa MEX lớn nhất có thể có của dãy thỏa mãn tính chất đã cho.

Ví dụ:

Solution:

Với tính chất của MEX ta suy ra dãy số cần tìm phải là dãy liên tục \(\lbrack 0,1,2,\ldots,i\rbrack\), lúc đó MEX là \(i + 1\). Như vậy ta sẽ tìm \(i\) sao cho \(0|1|\ldots|i\) là lớn nhất không vượt quá \(X\).

Phép Or của \(i\) số tự nhiên đầu tiên như sau

Ta thấy:

+ \(i\) càng lớn thì giá trị của phép OR càng lớn

+ Giá trị của phép OR có dạng \(2^{k} - 1\)

Do vậy:

+ Nếu \(X = 2^{k} - 1\) thì kết quả cần tìm là \(2^{k}\)

+ Nếu \(X < 2^{k} - 1\) thì kết quả là \(2^{k} - 1\), trong đó \(k\) là số nhỏ nhất có thể