Given a non-negative integer ~x~, please find a sequence of integers ~a_1, a_2, \ldots, a_n~ such that:

• ~0 \le a_i \le x~ for all ~1 \le i \le n~.

• AND-sum of every contiguous subsequence of ~a~ is pairwise different.

  Formally, denote ~f(l, r)=a_l \,\&\, a_{l+1} \,\&\, \ldots \,\&\, a_r~ (AND-sum of contiguous subsequence from position ~l~ to position ~r~). For all possible 4-tuple ~(l_1, r_1, l_2, r_2)~ such that ~l_1 \le r_1~, ~l_2 \le r_2~ and ~(l_1, r_1) \ne (l_2, r_2)~, we have ~f(l_1, r_1) \ne f(l_2, r_2)~.

• The length ~n~ is maximized.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10~) which is the number of test cases. The description of each test case is as follows.

Each test case consists of only integer ~x~ (~1 \le x \le 10^6~) — the upper bound of sequence ~a~ values.

Output

For each test case, print the answer in the following format:

The first line consists of an integer ~n~ (~1 \le n \le 2000~) — the length of sequence ~a~.

The second line consists of ~n~ integer ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le x~) — the elements of ~a~.

It can be shown that the length of sequence ~a~ that satisfies the problem's conditions can not exceed ~2000~.

Scoring

Sample Input 1

2
1
2

Sample Output 1

1
1
2
1 2

Notes

In the second test case, with ~a = [1, 2]~, we have:

• The subarray ~[1]~ has an AND-sum value of ~1~.

• The subarray ~[2]~ has an AND-sum value of ~2~.

• The subarray ~[1, 2]~ has an AND-sum value of ~1 \,\&\, 2 = 0~.

All three subarrays have distinct AND-sum values, so the sequence ~a~ satisfies the requirements of the problem. It can be proven that there does not exist a sequence ~a~ with a length of ~3~ or more that satisfies the requirements of the problem.