On a mysterious OJ, Little C participated in $n$ contests, where in the $i$-th $(i=1, 2, \ldots, n)$ contest, he earned $a_i$ points. The points can be positive or negative, but they are guaranteed to be integers in the range $[-2, 2]$.

For some reason, Little C will choose a contiguous interval of contests $[l, r]$ and claim: "If I had only participated in the contests in this interval, my total score would be $\sum_{i=l}^r a_i$!" Naturally, Little C will choose at least one contest, and the sum of points in the chosen interval is the maximum among all possible intervals. This maximum sum is his satisfaction level with his performance.

As time passed, Little C gradually forgot the scores of each contest and his satisfaction level. He only remembers how many contests he played for each possible score. Little C wants to know what the minimum possible value of his satisfaction level could be, and he has come to you for help.

Input

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

Each of the following $T$ lines contains five non-negative integers $c_{-2}, c_{-1}, c_0, c_1, c_2$, representing the number of contests for each score. You can calculate $n = c_{-2} + c_{-1} + c_0 + c_1 + c_2$ yourself.

Output

For each test case, output two lines. The first line contains an integer representing the minimum possible value of Little C's satisfaction level.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, representing any one possible sequence of contest scores that achieves this minimum value.

Examples

Input 1

1
1 1 0 2 2

Output 1

3
1 -1 2 -2 1 2

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases. For all data, it is guaranteed that $1 \le T \le 10000$ and $1 \le n, \sum n \le 5 \times 10^5$.