CF2179D Blackslex and Penguin Civilization

Penguins are civilized creatures that communicate using permutations. Blackslex, as a penguin researcher, must study their means of communication. For a given integer $ n $ , consider permutations $ ^{\text{∗}} $ $ p $ of the array $ [0, 1, \ldots, 2^n - 1] $ . Define $$$ S(p) \;=\; \sum_{i=0}^{2^n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr), $$$ where $ \operatorname{popcount}(z) $ is the number of $ 1 $ -bits in the binary representation of $ z $ (for instance, $ \operatorname{popcount}(5) = 2 $ because $ 5 = 101_2 $ has two $ 1 $ -bits in the binary representation), and $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). . A permutation is considered sacred if it maximizes $ S(p) $ . Find the lexicographically minimal $ ^{\text{†}} $ sacred permutation. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^{\text{†}} $ An array $ a $ is lexicographically smaller than an array $ b $ of the same size if and only if the following holds: - in the first position where $ a $ and $ b $ differ, the array $ a $ has a smaller element than the corresponding element in $ b $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 16 $ ) — the number of test cases. Each test case contains a single integer $ n $ ( $ 1 \le n \le 16 $ ). It is guaranteed that the sum of $ 2^n $ over all test cases does not exceed $ 2^{16} $ .

For each test case, output $ 2^n $ integers $ p_0, p_1, \ldots, p_{2^n-1} $ — the required permutation.

For the first test case, there are two possible permutations. - $ p = [0, 1] $ , $ S(p) = 0 $ - $ p = [1, 0] $ , $ S(p) = 1 $ For the second test case, $ S([3, 1, 0, 2]) = 3 $ is sacred. There are other permutations $ p $ that are sacred, such as $ p = [3, 2, 0, 1] $ , but those are not lexicographically minimal.