思路

简单签到，因为他说 $x_i$ 的奇偶性只要与 $i$ 的奇偶性相同即可，也就是说 $x_i$ 可以无限大，那么不难想到，若一个为奇数，一个为偶数，则第一次到为奇数的坐标，第二次到偶数的坐标，如果要到 $(3,4)$ 这个点，则 $(1,1)-(3,1)-(3,4)$。如果要到 $(6,5)$，则 $(1,1)-(1,5)-(6,5)$，两种情况可以证明都只需要两步，所以得出第一个结论，当 $n$ 与 $m$ 的奇偶性不同时，则直接输出 $2$。如果奇偶性相同呢，不难发现，当两个数都为奇数时，只要让一个数做两次即可，因为当 $i$ 为 $1$ 时，其中一个奇数可以直接到达，而另一个数需要加一次偶数再加一次奇数完成。例如要到 $(5,7)$ 这个点，则其中一种方法为 $(1,1)-(5,0)-(5,4)-(5,7)$。当两个数都为奇数时，方法相同，因为当 $i$ 为 $1$ 时，其中一个偶数可以先加上一个奇数，而另一个数就可以在下一次直接完成，到下次 $i$ 为奇数时前面那个只加了一个奇数的偶数就可以再加一个奇数，从而完成。例如要到 $(4,8)$ 这个点，则其中一种方法为 $(1,1)-(1,0)-(1,8)-(4,8)$，那么这两种奇偶性相同的情况就都只要输出 $3$ 即可。

最后总结一下结论：

• 当两个数奇偶性不同时输出 $2$。
• 当两个数奇偶性相同时输出 $3$。

每次判断时间复杂度为 $O(1)$，总时间复杂度为 $O(t)$，可以通过此题。

代码

#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;

signed main()
{
	int t;
	cin >> t;
	while(t--){
		int n, m;
		cin >> n >> m;
		if((n % 2 == 0 && m % 2 != 0) || (n % 2 != 0 && m % 2 == 0)){
			cout << 2 << endl;
		}
		else{
			cout << 3 << endl;
		}
	}
	return 0;
}