题目描述

Debbie, Debby, Debra and Deborah are going to play a game with marbles together. Debbie has brought $2^{d_{1}}$ marbles, Debby -- $2^{d_{2}}$ marbles, Debra -- $2^{d3}$ marbles, while Deborah -- $2^{d4}$ marbles. The kids have gathered their marbles into a single pile containing $2^{d_{1}} + 2^{d_{2}} + 2^{d_{3}} + 2^{d_{4}}$ marbles, and the game is starting.

The game consists of turns. Each turn consists of two steps:

The kids choose any of their piles with more than one marble and divide it into two non-empty piles. That is, if the chosen pile contains $m \ge 2$ marbles, the new piles must contain $m_{1}$ and $m_{2}$ marbles where $m_1$ and $m_2$ are positive integers, and $m_{1} + m_{2} = m$ .

If there are several piles with the same number of marbles, only one of these piles is kept, while all the others with this number of marbles are discarded (thrown away).

The game ends when only one pile is left, and this pile contains a single marble. The goal of the game is to end it in the least possible number of turns. Note that the game is cooperative, that is, the kids aren't playing against each other, but trying to reach a common goal together.

Help the kids and find the best way to play.

输入格式

The first line of the input contains a single integer $T$ -- the number of test cases $(1 \le T \le 500)$ .

Each of the next $T$ lines describes one test case and contains four non-negative integers $d_{1}, d_{2}, d_{3}, d_{4} (0 \le d_{i} \le 20)$ .

输出格式

For each test case, output an integer $t$ -- the smallest number of turns required to end the game.

Then, output $t$ turn descriptions, in the order the turns should be made. Each description should consist of three integers $m , m_{1}, m_{2}$ -- the size of the divided pile and the sizes of the new piles, respectively $(m \ge 2$ ; $m_{1} > 0$ ; $m_{2} > 0$ ; $m_{1} + m_{2} = m)$ . Note that a pile of size $m$ must exist at that moment, and at the end of the game there should be only one pile left and that pile should contain a single marble.

2
1 0 1 0
0 1 2 3

3
6 2 4
4 2 2
2 1 1
5
15 10 5
10 5 5
5 1 4
4 2 2
2 1 1

提示

Time limit: 3 s, Memory limit: 512 MB.