I. Min Xor Subarray
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of length $$$n$$$ is defined as a sequence of integers from $$$0$$$ to $$$n-1$$$, each number appearing exactly once. We define a XUM value for any permutation of length $$$n$$$ as the SUM of XOR of all subarrays with length $$$\ge 2$$$. The problem is, for a given $$$n$$$, you have to find some permutation for which this XUM value is minimum among all the possible permutations of length $$$n$$$. But we found this problem to be easy.

Hence, the problem is divided into two tasks. In task $$$1$$$, you have to print $$$n$$$ integers $$$(0$$$ to $$$n-1)$$$, a permutation for which this XUM value is minimum among all the possible permutations. In task $$$2$$$, you have to print only one integer, the minimum XUM value for any permutation among all the possible permutations.

$$$\dagger$$$ An array b is a subarray of an array a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1$$$ $$$\le$$$ $$$t$$$ $$$\le$$$ $$$10^5)$$$ — the number of test cases.

Each test case contains $$$2$$$ integers $$$c$$$ and $$$n$$$ $$$(1$$$ $$$\le$$$ $$$c$$$ $$$\le$$$ $$$2$$$ $$$,$$$ $$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$10^9)$$$.

Additional constraint on the input: The sum of $$$n$$$ over all the test cases with $$$c=1$$$ does not exceed $$$2⋅10^5$$$.

Output

For test cases with $$$c=1$$$, you have to solve task $$$1$$$. Print a permutation of $$$n$$$ integers, $$$0$$$ to $$$n-1$$$, each appearing once for which the XUM value would be minimum.

For test cases with $$$c=2$$$, you have to solve task $$$2$$$. Print $$$1$$$ integer, the minimum XUM value among all the permutations of length $$$n$$$. Since this value can be very large, print it modulo $$$10^9+7$$$.

Example
Input
5
2 1
1 3
2 4
1 5
2 10
Output
0
2 0 1 
12
4 0 2 3 1
212