### 问题描述 小夜在一次探险中，发现了一个神秘的石板拼图。这个拼图是由一个包含 $N$ 行和 $M$ 列的网格构成的。她有两种形状的石板，一种是 $2×2$ 的大石板，另一种是 $1×1$ 的小石板。她需要用这两种石板去填充整个网格，以完成拼图。每个网格单元只能被一个石板覆盖，并且小夜希望尽可能地减少使用小石板的数量。 请你帮助小夜计算出，要完成这个神秘石板拼图，最少需要使用多少个 $1×1$ 的小石板。 ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包含一行，包含两个空格分隔的整数 $N$ 和 $M$，分别表示网格的行数和列数。 ### 输出格式 对于每个测试用例，输出一行，表示完成拼图最少需要使用的 $1×1$ 小石板的数量。 ### 输入样例 ```text 4 1 1 4 5 6 8 3 2 ``` ### 输出样例 ```text 1 4 0 2 ``` ### 说明 测试用例 1：网格只有一个单元，所以必须使用一个 $1×1$ 的小石板来填充。 测试用例 2：可以使用 $5$ 个 $2×2$ 的大石板和 $4$ 个 $1×1$ 的小石板来填充网格，所以最少需要使用 4 个小石板。 ### 评测数据范围 $1 \leq T\leq 10^4$。 $1\leq N,M\leq 10^4$。