春天，冰雪融化，万物复苏。
zxh 来到了乡村。
乡村是一个矩形，有 个路口，排成一个点阵，任意四连通的两个路口之间都有一条路相连。这些路围成了 个方格。
zxh 想要将所有道路种上花或草。但由于要保持整体的美观，每一个方格周围的四条路，必须满足两条路种了花，另两条路种了草。
由于 zxh 觉得花比草要好看，所以想问你，最多能有多少条路被种上花？
另外，对于比较小的乡村，zxh 想要知道任意一种构造方式。具体见【输出格式】。
本题使用多组数据。
第一行，一个整数 ，表示数据组数。
接下来 行，每行两个整数 ，表示点阵的长和宽分别是 ，且当前点输出方式为 。
对于每组数据：
第一行一个整数 表示答案。
若 ，接下来输出构造方案。
构造方案共 行，每行四个整数 表示 到 间有一条边种上了花。
其中 的意思是第 行第 列的点（编号均从 开始）。
3 0 2 2 0 2 3 0 3 3
8 11 14
1 1 1 2
4 1 1 2 1 1 3 2 3 2 1 2 2 2 2 2 3
本题采用捆绑测试。
特殊性质 A：。
特殊性质 B： 均为偶数。
特殊性质 C：保证 。
对于 的数据，。
保证同一测试点内，所有 的测试点满足 。
