NEXT SPARSE BINARY NUMBER:(GEEKSFORGEEKS)

Given an integer n in the input, find its next sparse binary number.A sparse binary number is a number whose binary representation does not contain any consecutive 1s.

Input:

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is number 'N'

Output:

Print next Sparse binary number,if the input number is not sparse else print the number itself.

Constraints:
1 ≤ T ≤ 100
1 ≤ n ≤ 100000

Example:

Input
2
3
5

Output
4
5

CODE:

#include <stdio.h>

int isSparse(int n)

{

   int k=n>>1;

    if(n & k)

      {return 0;}

    else

     { printf("%d\n",n);return n;}

}

int main() {

 int t,n,i; int k;

 scanf("%d",&t);

 for(i=0;i<t;i++)

 {

     scanf("%d",&n);

     while(1)

   {

      if (isSparse(n))

        {

          break;

        }

      else 

         n++;

   }

  

}

return 0;

}