题目描述

给定一个大小为 $n \times m$ 的棋盘（即 $n$ 行 $m$ 列），初始为空。你需要在这个棋盘上放置国际象棋中的棋子——马。

具体来说，你每次需要选择两个不同的空格子，在其上放置一对马（两个格子各一匹马），使得这一对马能够互相攻击。

根据如上规则，你最多可以放置多少对马？试构造方案以最大化马的数量。

【提示】

如下图所示，在国际象棋中，位于红色位置的一匹马，（在一步内）可以攻击（吃掉）黑色位置的马：

输入格式

本题单测试点包含多组数据。

第一行输入一个整数 $t$ ，表示数据组数。

对于每组数据，输入仅一行，包含两个整数 $n$ 和 $m$ ，分别表示棋盘的行数和列数。

输出格式

对于每组数据，第一行输出一个整数 $k$ （ $0 \le k \le \lfloor \dfrac{nm}{2} \rfloor$ ），表示所放置马的对数的最大值。

紧接着输出 $k$ 行，第 $i$ 行包含四个整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ （ $1 \le x_{i,1},x_{i,2} \le n$ ， $1 \le y_{i,1},y_{i,2} \le m$ ），表示你第 $i$ 次所选定的位置为 $(x_{i,1},y_{i,1})$ 及 $(x_{i,2},y_{i,2})$ （其中 $(x,y)$ 表示第 $x$ 行第 $y$ 列的格子）。

若有多种满足题意的方案，输出其中任意一组即可。

数据范围

对于 $100\%$ 的数据， $1 \le t \le 10^4$ ， $1 \le n,m \le 1000$ ， $\sum{(n \cdot m)} \le 10^6$ （即 $t$ 组数据的棋盘格子数量总和不超过 $10^6$ ）。

本题共 $20$ 个测试点，各测试点的具体限制如下：

输入样例 1

5
1 2
2 3
3 3
2 4
2 6

输出样例 1

0
2
1 1 2 3
2 1 1 3
4
1 1 2 3
3 1 1 2
3 3 2 1
1 3 3 2
4
1 1 2 3
2 1 1 3
1 2 2 4
2 2 1 4
4
1 1 2 3
2 2 1 4
1 6 2 4
1 3 2 5

样例解释

对于第一组数据，显然你无法放置任何棋子，故答案为 $0$ 。

对于第二组数据，你可以将第一对棋子放置在 $(1,1)$ 和 $(2,3)$ 这两个位置上，然后将第二对放置在 $(2,1)$ 和 $(1,3)$ 上。由于棋盘上不存在可以攻击 $(1,2)$ 和 $(2,2)$ 的位置，你无法在这两个位置上放置棋子。综上，答案为 $2$ 。