Kitchen Duty Roster

Statement

A \(d\)-day event was attended by \(n\) people. We will number the people from \(0\) to \(n-1\) arbitrarily.

On each day, \(k\) of those \(n\) people had kitchen duty.

Once the event was over, one of the attendees observed two peculiar properties:

• No two days had the exact same kitchen crew.
• No two days had completely disjoint kitchen crews. (In other words, for any two days there is at least one person who was in the kitchen on both of those days.)

Given \(n\) and \(k\), determine the maximum \(d\). For some test cases, also construct one possible kitchen duty roster.

Input format

The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.

Each test case consists of a single line with three integers \(n\), \(k\), and \(p\). Here, \(p=1\) means that you should also print one optimal kitchen duty roster and \(p=0\) means that you are just computing the optimal \(d\).

Output format

For each test case output a single line with the corresponding \(d\).

Then, if \(p=1\), output another \(d\) lines, the \(i\)-th of which contains \(k\) space-separated numbers: the numbers of people who had kitchen duty on day \(i\).

If there are multiple optimal solutions, you may output any one of them. Within each line the numbers can appear in any order.

Subproblem K1 (20 points, public)

Input file: K1.in

Constraints: \(1\leq k\leq n\leq 4\) and all tests are distinct.

Subproblem K2 (10 points, public)

Input file: K2.in

Constraints: \(t=1\), \(n=7\), \(k=5\).

Subproblem K3 (10 points, public)

Input file: K3.in

Constraints: \(t=1\), \(n=7\), \(k=2\).

Subproblem K4 (30 points, secret)

Input file: K4.in

Constraints: \(t=100\), \(1\leq k\leq 5\), \(20\leq n\leq 60\).

Additionally, it is guaranteed that the correct output file has at most \(100\,000\) lines.

Subproblem K5 (30 points, secret)

Input file: K5.in

Constraints: \(t=100\), \(1\leq k\leq n\leq 60\).

Additionally, it is guaranteed that the correct output file has at most \(100\,000\) lines.

Example

4
3 2 1
3 2 0
10 1 1
8 3 0

3
0 1
1 2
2 0
3
1
6
21

For \(n=3\) and \(k=2\) there are only three possible kitchen crews. Having three days, each with one possible kitchen crew, is a valid solution. (E.g., note that for days 2 and 3 both kitchen crews contain person 2.) Therefore, this must be an optimal solution.

The second test case is the same as the first but now we are just printing the optimal \(d\) without printing a roster.

In the third test case if we had more than one day, we would have to violate one of the two properties: either we would have the same (1-person) crew on two days, or we would have two days on which the crews don’t share any person. Hence, the printed solution “there was 1 day and on that day person 6 had kitchen duty” is optimal.