As we know, Rikka is poor at math. Yuta is worrying about this situation, so he asks rikka to have some practice on codeforces. Then she opens the problem B:
Given an integer K, she needs to come up with an sequence of integers A satisfying that the number of different continuous subsequence of A is equal to k.
Two continuous subsequences a, b are different if and only if one of the following conditions is satisfied:
The length of a is not equal to the length of b.
There is at least one t that at≠bt, where at means the t-th element of a and bt means the t-th element of b.
Unfortunately, it is too difficult for Rikka. Can you help her?
There are at most 20 testcases，each testcase only contains a single integer K (1≤K≤109)
For each testcase print two lines.
The first line contains one integers n (n≤min(K,105)).
The second line contains n space-separated integer Ai (1≤Ai≤n) - the sequence you find.
1 2 3 4