SP7323 CHEFJUL - Happy Days

Johnny 在他的花园里有一个池塘，池塘中有一些小岛。在这些岛屿之间，有一些桥梁将它们连接起来。每一座桥都可以被移除。每天，Johnny 会移除一些桥梁，以便在任何两个岛屿之间只存在唯一一条路径。到了晚上，他会把移除的桥梁重新放回原位。此外，Johnny 有一些特别喜欢的桥，他永远不移除这些桥。某一天，如果 Johnny 可以创造出一种之前从未有过的桥梁配置，他就会感到快乐。你的任务是计算出Johnny 可以享受这种快乐的天数。当然，如果那些特别喜欢的桥本身就不满足让 Johnny 感到快乐的条件，那么他就一天也不会快乐。

输入的第一行是一个整数 $t$，表示测试用例的数量。接下来是每个测试用例的具体描述。每个测试用例的第一行是一个整数 $n$，表示岛屿的数量，编号为 $1$ 到 $n$。接下来的 $n$ 行，每行包含 $n$ 个字符，这些字符组成了岛屿的连通矩阵。如果第 $y$ 行第 $x$ 列的字符是 `1`，说明编号为 $x$ 和 $y$ 的岛屿之间有桥连接；如果是 `0`，则没有桥连接。接下来一行是一个整数 $p$，表示喜欢的桥的数量。接下来有 $p$ 行，每行包含两个整数，表示由喜欢的桥连接的岛屿对。

对于每个测试用例，输出一个整数，代表在这种情况下 Johnny 可以开心的天数。

- $1 \le t \le 1000$ - $2 \le n \le 15$ - $0 \le p \le \frac{n(n-1)}{2}$ **本翻译由 AI 自动生成**