# Increasing Sequence with Fixed OR

## Problem Statement

<br>

You are given a positive integer $$n$$𝑛. Find the longest sequence of positive integers $$a=\[a1,a2,…,ak]$$𝑎=\[𝑎1,𝑎2,…,𝑎𝑘] that satisfies the following conditions, and print the sequence:

* $$ai≤n$$𝑎𝑖≤𝑛 for all $$1≤i≤k$$1≤𝑖≤𝑘.
* $$a$$𝑎 is strictly increasing. That is, $$ai>ai−1$$𝑎𝑖>𝑎𝑖−1 for all $$2≤i≤k$$2≤𝑖≤𝑘.
* $$ai|ai−1=n$$𝑎𝑖|𝑎𝑖−1=𝑛 for all $$2≤i≤k$$2≤𝑖≤𝑘, where $$|$$| denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$t$$𝑡 ($$1≤t≤1000$$1≤𝑡≤1000). Description of the test cases follows.

The only line of each test case contains one integer $$n$$𝑛 ($$1≤n≤1018$$1≤𝑛≤1018).

It's guaranteed that the sum of lengths of the longest valid sequences does not exceed $$5⋅105$$5⋅105.

Output

For each testcase, print two lines. In the first line, print the length of your constructed sequence, $$k$$𝑘. In the second line, print $$k$$𝑘 positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.

ExampleinputCopy

```
4131423
```

outputCopy

```
1
1
3
1 2 3
4
4 10 12 14
5
7 18 21 22 23
```

## Intuition

```
Check Initially

If

    // 23
    // 10111

    // 00101 5
    // 10010 18
    // 10101 21
    // 10110 22
    // 10111 23

If in 5 we put 1 initially, then we will have to put one in 18 also
Due to sum condition

So like that we generate the nums,

We get a alternating pattern 

Code is difficult refer it
```

### Links

<https://codeforces.com/contest/1988/problem/C>

### Video Links

<https://www.youtube.com/watch?v=sAUI0T6r9TA&t=1161s&ab_channel=CompetitiveProgrammingwithShayan>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
#include<bits/stdc++.h>
using namespace std;

int main(){

    int t;
    while(t--){
        int n;
        cin>>n;

        if(__builtin_popcountll(n) == 1){
            cout<<"1\n"<<n<<endl;
            continue;
        }

        int res = __builtin_popcountll(n) + 1;
        cout<<res<<endl;

    // 23
    // 10111

    // 00101 5
    // 10010 18
    // 10101 21
    // 10110 22
    // 10111 23
        for(int i=0; i<res; i++){
            int cnt = 0, cur = 0;
            int val = 0;

            for(int l = 64; l>=0; l--){
                if(n & (1ll<<l)){
                    cnt ++;
                    /*
                    Basically, Only i ones will get printed, 
                    When i = 0
                    Initial ones not printed, 
                    When i = 1, only initial one printed, then alternating because of curr
                    For zero we just ignore
                    Only at one we do alternating

                    Refer Explanation for more
                    */ 
                    
                    if(cnt <= i)
                        val += (1ll<<l);
                    else{
                        if(cur)
                            val += (1ll<<l);
                        cur = 1-cur;
                    }
                }
            }

            cout<<val<<" ";
        }  

        cout<<endl;
    }
}
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###