C. Constructing Box Projections
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a positive integer $$$d$$$, let $$$[d]=\{1,2,\dots,d\}$$$. You are given three positive integers $$$a,b,c$$$.

Construct a set $$$S\subseteq[a]\times[b]\times[c]$$$ of integer triples satisfying all of the following conditions:

  • for every $$$(x,y)\in[a]\times[b]$$$, at least one triple $$$(x,y,z)$$$ belongs to $$$S$$$;
  • for every $$$(x,z)\in[a]\times[c]$$$, at least one triple $$$(x,y,z)$$$ belongs to $$$S$$$;
  • for every $$$(y,z)\in[b]\times[c]$$$, at least one triple $$$(x,y,z)$$$ belongs to $$$S$$$.

In other words, deleting any one coordinate from the triples in $$$S$$$ must produce every possible pair of the other two coordinates. The size $$$|S|$$$ must be as small as possible.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 100$$$), the number of test cases.

For each test case, one line contains three integers $$$a,b,c$$$ ($$$1\le a\le 100$$$, $$$1\le b\le 100$$$, $$$1\le c\le 100$$$).

Output

For each test case, print several lines:

  • The first line contains one integer $$$m$$$, the minimum possible value of $$$|S|$$$.
  • Each of the next $$$m$$$ lines contains three integers $$$x,y,z$$$, describing one triple in $$$S$$$.

The $$$m$$$ triples must be pairwise distinct. Their order does not matter. If several minimum-size sets are valid, output any one of them.

Example
Input
2
1 1 1
2 2 2
Output
1
1 1 1
4
1 1 1
1 2 2
2 1 2
2 2 1
Note

The sample output is one possible answer. Other valid minimum-size sets are also accepted.