32462번 - Construct a Coin Set 스페셜 저지다국어

문제

The change-making problem is the problem of finding the minimum number of coins that add up to the change to be returned after purchasing items at a shop. A coin set refers to a collection of coin values available for making the change. The greedy algorithm for the change-making problem repeatedly selects the largest coin value among the coin set that does not exceed the remaining amount of change. This process continues until the total amount of change is made.

An optimal solution refers to a solution that uses the fewest number of coins. However, the greedy algorithm does not always guarantee an optimal solution. Under certain conditions, the greedy algorithm may give a non-optimal solution.

Given a positive integer $N,ドル your task is to find a coin set for which the greedy algorithm returns an optimal solution for all amounts from 1ドル$ won to $(N-1)$ won, but not for $N$ won. Notice that the coin whose value is 1ドル$ is always in the coin set.

입력

The first line of input contains the number of test cases $T$. Each of the next $T$ lines of input contains a single integer $N$.

출력

For each test case,

If it is impossible to construct a coin set satisfying the conditions given in the problem, print $-1$.

If it is possible to construct a coin set, print the size of the coin set $K$ in the first line. In the next line, print the coin values $a_{1},a_{2},\ldots ,a_{K},ドル separated by spaces in increasing order. The size of the coin set does not have to be a minimum.

제한

• 1ドル\le T\le 1,円 000$
• 1ドル\le N\le 10^{9}$
• 1ドル\le K\le 30$
• 1ドル=a_{1}<a_{2}<\cdots <a_{K}\le 10^{9}$

노트