P10563 [ICPC 2024 Xi'an I] Yet Another Maximum Matching Counting Problem

在一个二维平面上， 你有一组点 $\{(x_i,y_i)\}$，满足 $1\le x_i\le n, 1\le y_i\le m$（$x_i$ 和 $y_i$ 都是整数），并且没有两个点具有相同的坐标。 如果两个点具有相同的水平或垂直坐标，我们将在这两个点之间连接一条边。这将形成一个图。 你需要找到由所有可能的 $2^{nm}-1$ 个非空集合形成的图中的最大匹配数之和，并输出结果对 $998244353$ 取模。 在这里，图中的最大匹配数定义为：选择最多的边，使得任何两条边之间没有公共顶点。

这个问题有多个测试用例。 第一行包含一个整数 $T(1\le T\le 100)$，表示测试用例的数量。 每个测试用例包含两个整数 $n,m(1\leq n,m\leq 500)$。

对于每个测试用例，输出一个整数，表示结果对 $998244353$ 取模。

（由 ChatGPT 4o 翻译）