Fashion Police (Small)

You are so excited about the 2016 Code Jam World Finals that you just moved to New York. You have brought along $J$ different jackets (numbered $1$ through $J$), $P$ different pairs of pants (numbered $1$ through $P$), and $S$ different shirts (numbered $1$ through $S$). You have at least as many shirts as pairs of pants, and at least as many pairs of pants as jackets ($J \le P \le S$).

Every day, you pick one jacket, one pair of pants, and one shirt to wear as an outfit. You wash all of your garments every night, so every garment is available each day.

In New York, the Fashion Police officers watch and record what everyone wears every day. If they find out that you have worn the exact same outfit twice, you are immediately taken to the Fashion Jail on 5th Avenue for a mandatory makeover, and you definitely want to avoid that. You are also immediately taken to Fashion Jail if they find out that you have worn the same two-garment combination more than $K$ times in total. A combination is a particular jacket worn with a particular pair of pants, a particular jacket worn with a particular shirt, or a particular pair of pants worn with a particular shirt. For example, in the set of outfits (jacket 1, pants 2, shirt 3) and (jacket 1, pants 1, shirt 3), the combination (jacket 1, shirt 3) appears twice, while the combination (pants 1, shirt 3) appears only once.

You wear one outfit per day. Find the largest possible number of days you can avoid being taken to Fashion Jail, and produce a list of outfits to wear on those days.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of one line with four integers $J$, $P$, $S$, and $K$.

Limits

• $1 \le T \le 100$
• $1 \le J \le P \le S$
• $1 \le K \le 10$
• $S \le 3$

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of days you can avoid being taken to Fashion Jail. Then output y more lines, each with three integers: the numbers of the jacket, pants, and shirt (in that order) for one day's outfit.

An outfit $(a_1, b_1, c_1)$ comes before an outfit $(a_2, b_2, c_2)$ if it is smaller in lexicographic order: compare the jacket numbers first, then the pants numbers, then the shirt numbers. Print the outfits sorted in this order. Several sets of $y$ outfits can avoid Fashion Jail; among them, output the set whose sorted list is lexicographically smallest when two lists are compared outfit by outfit from the start.

In Case #1, even though the Fashion Police officers have set a lenient $K$ value of 10, you can form only one outfit, so you can avoid Fashion Jail for only one day.

In Case #2, adding any other outfit would send you to Fashion Jail:

• Adding 1 1 3 would use the combination (jacket 1, pants 1) more than 2 times.
• Adding 1 2 3 would use the combination (jacket 1, pants 2) more than 2 times.

In this case, every set of 5 outfits includes at least one fashion violation.

The numbers of the jacket, pants, and shirt within one outfit do not have to be in nondecreasing order the way $J$, $P$, and $S$ are.

In Case #3, you have only one jacket and pants combination, which you must keep reusing, so no matter which shirts you wear, you cannot form more than $K = 2$ different outfits.

In Case #4, the outfits 1 1 3 and 1 2 1 also avoid Fashion Jail for 2 days, but 1 1 1 and 1 2 2 form the lexicographically smallest list, so that set is the answer.