Video Approach:


Read problem statements.

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

  • The MEX of [2,2,1] is 0, because 0 does not belong to the array.
  • The MEX of [3,1,0,1] is 2, because 0 and 1 belong to the array, but 2 does not.
  • The MEX of [0,3,1,2] is 4 because 0,1,2 and 3 belong to the array, but 4 does not.

Find the maximum possible MEX of an array of non-negative integers such that the bitwise OR of the elements in the array does not exceed X.

Input Format

  • The first line contains T denoting the number of test cases. Then the test cases follow.
  • Each test case contains a single integer X on a single line.

Output Format

For each test case, output on a single line the maximum possible MEX of the array satisfying the given property.

Constraints

  • 1≤T≤105
  • 0≤X≤109

Subtasks

Subtask 1 (100 points): Original constraints

Sample Input 1 

4
0
1
2
5

Sample Output 1 

1
2
2
4

Explanation

Test case 1: The array could be [0].

Test case 2: The array could be [0,1]. Here the bitwise OR of 0 and 1 is 1 and the MEX of the array is 2 as both 0 and 1 belong to the array.

Test case 4: The array could be [1,0,3,2]. Here the bitwise OR of all integers in the array is 3 and the MEX of the array is 4.


MEX-OR Solution: 

#include <iostream>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t--){
    int x, ans = 1;
    cin>>x;
    if(x == 0){
        cout<<1<<endl;
    }
    else if(x == 1 || x == 2){
        cout<<2<<endl;
    }
    else{
        while(ans*2 <= x){
            ans*=2;
        }
        if(ans == x){
            cout<<x<<endl;
        }
        else if(x ==(2*ans-1)){
            cout<<x+1<<endl;
        }
        else{
            cout<<ans<<endl;
        }
    }
}
return 0;
}