K. 餐券设计
time limit per test
1 秒
memory limit per test
512 MB
input
标准输入
output
标准输出

XCPC 的比赛主办方通常会为选手提供餐券，假设主办方计划为每位选手提供 k 张餐券，总面值 n 元。

主办方希望尽量避免找钱或多花钱的情况，因此这 k 张餐券能够恰好表示 的所有钱数。

同时主办方希望餐券纸张的印制数越少越好，因此 k 需要尽可能地小。

显然对于给定的总面值 n，餐券张数 k 有最小值 kmin，当 k = kmin 时可能有多种设计方案，你只需要为主办方提供餐券面值按从小到大排序后的字典序最小和最大的方案。

更准确地说，给定 n，从满足下列条件的序列 a1, a2, ..., ak 中：

  1. a1 + a2 + ... + ak = n
  2. 1 ≤ a1 ≤ a2 ≤ ... ≤ ak ≤ n
  3. 对 m = 1, 2, ..., n，可重集 {a1, a2, ..., ak} 都存在元素和为 m 的子集。

你需要找到 k 最小的序列，输出 k 的最小值 kmin 以及 k = kmin 时字典序最小和最大的序列。

Input

本题每个测试数据包含多组测试用例。

第一行，输入一个整数 T (1 ≤ T ≤ 104)，表示测试用例组数。

接下来 T 行，每行输入一个整数 n (1 ≤ n ≤ 109)，表示总面值 n 元。

Output

输出共 3T 行，对于每组测试用例，输出三行：

  • 第一行，输出一个整数，表示 k 的最小值 kmin。
  • 第二行，输出 kmin 个以空格相隔的整数，表示序列 a1, a2, ..., akmin 字典序最小的方案。
  • 第三行，输出 kmin 个以空格相隔的整数，表示序列 a1, a2, ..., akmin 字典序最大的方案。
Example
Input
2
3
5
Output
2
1 2
1 2
3
1 1 3
1 2 2
Note

样例解释如下：

第一组测试用例，n = 3：

  • k = 1 时，满足前两个条件的序列方案只有 {3}，不存在元素和为 m = 1, 2 的子集。
  • k = 2 时，满足前两个条件的序列方案只有 {1, 2}，元素和为 m = 1, 2, 3 的子集都存在。

因此 n = 3 时 kmin = 2，字典序最小的方案为 {1, 2}，字典序最大的方案为 {1, 2}。

第二组测试用例，n = 5：

  • k = 1 时，满足前两个条件的序列方案只有 {5}，不存在元素和为 m = 1, 2, 3, 4 的子集。
  • k = 2 时，满足前两个条件的序列方案有 {1, 4}, {2, 3}，其中 {1, 4} 不存在元素和为 m = 2, 3 的子集，{2, 3} 不存在元素和为 m = 1, 4 的子集。
  • k = 3 时，满足前两个条件的序列方案有 {1, 1, 3}, {1, 2, 2}，这两个方案的元素和为 m = 1, 2, 3, 4, 5 的子集都存在。

因此 n = 5 时 kmin = 3，字典序最小的方案为 {1, 1, 3}，字典序最大的方案为 {1, 2, 2}。