Chef loves saving money and he trusts none other bank than State Bank of Chefland. Unsurprisingly, the employees like giving a hard time to their customers. But instead of asking them to stand them in long queues, they have weird way of accepting money.
Chef did his homework and found that the bank only accepts the money in coins such that the sum of the denomination with any previously deposited coin OR itself can't be obtained by summing any two coins OR double of any coin deposited before. Considering it all, he decided to start with $1$ Chefland rupee and he would keep choosing smallest possible denominations upto $N$ coins. Since chef is busy with his cooking, can you find out the $N$ denomination of coins chef would have to take to the bank? Also find the total sum of money of those $N$ coins.

-----Input:-----
- First line has a single integer $T$ i.e. number of testcases.
- $T$ lines followed, would have a single integer $N$ i.e. the number of coins the chef is taking.

-----Output:-----
- Output for $i$-th testcase ($1 ≤ i ≤ T$) would have 2 lines.
- First line would contain $N$ integers i.e. the denomination of coins chef would deposit to the bank.
- Second line would contain a single integer i.e. the sum of all the coins chef would deposit.

-----Constraints:-----
- $1 ≤ T ≤ 700$
- $1 ≤ N ≤ 700$

-----Subtasks:-----
- $20$ points: $1 ≤ T, N ≤ 80$
- $70$ points: $1 ≤ T, N ≤ 500$
- $10$ points: $1 ≤ T, N ≤ 700$ 

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
1
1
1 2
3
1 2 4
7
1 2 4 8
15

-----Explanation:-----
For testcase 1: First coin is stated to be 1, hence for $N$ = 1, 1 is the answer.
For testcase 2: Since chef chooses the lowest possible denomination for each $i$-th coin upto $N$ coins, second coin would be 2. Only sum possible with N = 1 would be 1+1 = 2. For N = 2, $\{1+2,  2+2\}$ $\neq$ $2$.
For testcase 3: With first two coins being 1 and 2, next coin couldn't be 3 because 3+1 = 2+2, but $\{4+1,  4+2,  4+4\}$ $\neq$ $\{1+1,  1+2,  2+2\}$

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'try:\r\n    from collections import Counter\r\n    from sys import stdin, stdout\r\n    def get_ints(): return map(int, stdin.readline().strip().split())\r\n    def get_list(): return list(map(int, stdin.readline().strip().split()))\r\n    def get_string(): return stdin.readline().strip()\r\n    def get_singleInt(): return int(stdin.readline())\r\n    def main():\r\n        testCases=get_singleInt()\r\n        a=reqNumbers()\r\n        for i in range(testCases):\r\n            limit=get_singleInt()\r\n            for i in range(limit):\r\n                print(a[i],end=" ")\r\n            print()\r\n            print(sum(a[:limit]))\r\n\r\n    def reqNumbers():\r\n        reqList = [1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998,\r\n                   4297, 4433, 4779, 4851, 5123, 5243, 5298, 5751, 5998, 6374, 6801, 6925, 7460, 7547, 7789, 8220, 8503, 8730, 8942, 9882, 10200, 10587, 10898, 11289, 11614, 11876, 12034, 12931, 13394, 14047, 14534, 14901, 15166, 15688, 15972, 16619, 17355]\r\n        return reqList\r\n        """uniqueList=[]#for storing all such values\r\n        lis1=[]#for storing all the sum values and double of those values\r\n        uniqueList.append(1)\r\n        uniqueList.append(2)\r\n        uniqueList.append(4)\r\n        lis1.append(2)\r\n        lis1.append(4)\r\n        lis1.append(8)\r\n        lis1.append(3)\r\n        lis1.append(5)\r\n        lis1.append(6)\r\n        for number in range(5,100000):\r\n            lis2 = []  # for storing the sums obtained by summing with current denomination \r\n            x=number\r\n            for i in range(len(uniqueList)):\r\n                lis2.append(x+uniqueList[i])\r\n            lis2.append(x+x)\r\n            count=0\r\n            for j in range(len(lis2)):\r\n                f=lis2[j]\r\n                if f in lis1:\r\n                    pass\r\n                else:\r\n                    count=count+1\r\n            if count==len(lis2):               \r\n                uniqueList.append(x)\r\n                lis1.append(x+x)\r\n                for k in range(len(uniqueList)-1):\r\n                    lis1.append(x+uniqueList[k])\r\n                print(x)\r\n        print(len(uniqueList))\r\n        return uniqueList"""\r\n\r\n    def __starting_point():\r\n        main()\r\nexcept Exception:\r\n    pass\r\n\r\n\r\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15453