你对 2016 年 Code Jam 全球总决赛感到非常兴奋，于是你搬到了纽约。你带了 $J$ 件不同的夹克（编号为 1 到 $J$）、$P$ 条不同的裤子（编号为 1 到 $P$）以及 $S$ 件不同的衬衫（编号为 1 到 $S$）。你拥有的衬衫数量至少与裤子数量一样多，裤子数量至少与夹克数量一样多（$J \le P \le S$）。

每天，你都会选择一件夹克、一条裤子和一件衬衫作为一套服装。你每天晚上都会清洗所有的衣物，因此所有的衣物每天都可以使用。

在纽约，时尚警察时刻关注并记录着每个人每天的穿着。如果他们发现你穿过完全相同的服装两次，你将立即被带到位于第五大道的时尚监狱接受强制改造；你绝对想避免这种情况！如果他们发现你穿过相同的两件套组合超过 $K$ 次，你也会立即被带到时尚监狱。一个组合是指：特定的夹克搭配特定的裤子、特定的夹克搭配特定的衬衫，或者特定的裤子搭配特定的衬衫。例如，在服装组合（夹克 1，裤子 2，衬衫 3）和（夹克 1，裤子 1，衬衫 3）中，组合（夹克 1，衬衫 3）出现了两次，而组合（裤子 1，衬衫 3）只出现了一次。

你每天穿一套服装。你能算出在不被带到时尚监狱的情况下，你最多可以穿多少天，并列出每天使用的服装清单吗？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例由一行包含四个整数 $J, P, S$ 和 $K$ 组成。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个整数：在不被带到时尚监狱的情况下，你能够坚持的最长天数。然后输出 $y$ 行，每行包含三个整数：该天服装的夹克、裤子和衬衫编号（按此顺序）。服装列表可以以任何顺序排列，但这些服装不能导致你如上所述被带到时尚监狱。

如果存在多种答案，你可以输出其中任意一种。

数据范围

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

样例

样例输入 1

4
1 1 1 10
1 2 3 2
1 1 3 2
1 2 3 1

样例输出 1

Case #1: 1
1 1 1
Case #2: 4
1 1 2
1 2 3
1 2 1
1 1 1
Case #3: 2
1 1 2
1 1 1
Case #4: 2
1 1 3
1 2 1

说明

样例输出展示了针对样例测试用例的一组答案。可能存在其他答案。

在 Case #1 中，尽管时尚警察设置了宽松的 $K$ 值为 10，但你只能搭配出一种可能的服装，因此你只能避免进入时尚监狱一天。

在 Case #2 中，添加任何其他服装都会导致你进入时尚监狱： 添加 1 1 3 会导致组合（夹克 1，裤子 1）使用超过 2 次。 添加 1 2 2 会导致组合（夹克 1，裤子 2）使用超过 2 次。 在这种情况下，任何 5 套服装的组合都会包含至少一次时尚违规。

请注意，单套服装中夹克、裤子和衬衫的编号不必像 $J, P$ 和 $S$ 那样按非递减顺序排列。

在 Case #3 中，你只有一种夹克+裤子的组合，必须反复使用，所以无论你穿哪件衬衫，你都无法组成超过 $K = 2$ 种不同的服装。

在 Case #4 中，另一个可能的最长服装集合是：

1 2 2
1 1 1