Nearest Numbers with the Same Number of Set Bits

Given a positive integer n, your task is to determine the next smallest integer and the previous largest integer that have the same number of '1' bits in their binary representation as n.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next line of each test case consists of a single line containing the integer ‘n’.

Output:

For each test case, print the next smallest integer and the previous largest integer to ‘n’ with the exact number of ‘1’ bits set.
The output for each test case should be printed on a new line.

Example:

Input:

n = 6

Output:

{9, 5}

Explanation:

The binary representation of 6 is ‘0110’, which has two ‘1’ bits set.
The next smallest integer is 9 (binary ‘1001’), the smallest integer greater than 6 having two ‘1’ bits set.
The previous largest integer is 5 (binary ‘0101’), the largest integer smaller than 6 having two ‘1’ bits set.
Therefore, the answer is {9, 5}.

Constraints:

• 1 <= T <= 10000
• ‘n’ can have 30 bits at max

Note:

1. ‘n’ is a positive integer greater than one.
2. For any given integer ‘n’, there is always a positive integer smaller than ‘n’ having the exact number of ‘1’ bits set.
3. Don’t print anything. Just implement the function and return the answer.
4. ‘n’ can have a max of ‘30’ bits.