Roundgod 和 kimoyami 正在一个有向图上玩图游戏。给定一个有向图 $G = (V, E)$ 和一个源顶点 $s \in V$，图游戏 $(G, s)$ 定义如下：

最初，标记位于源顶点 $s$ 上。Roundgod 和 kimoyami 轮流沿着有向边移动标记，Roundgod 先手。当任一玩家无法进行有效移动时游戏结束，无法移动的玩家输掉游戏。如果游戏持续了 $10^{100}$ 回合，则该游戏被视为平局。

Roundgod 并不擅长这个游戏，经常被 kimoyami 击败。他想起了那句名言：“如果你不能打败他们，就加入他们！”，于是他提出了图游戏“连接（join）”的概念。给定一个非空集合，包含 $k(k > 0)$ 个图游戏 $(G_1, s_1), \dots, (G_k, s_k)$。这 $k$ 个游戏的连接也是一个游戏，定义如下：

Roundgod 和 kimoyami 轮流在所有 $k$ 个图游戏中同时移动标记，Roundgod 先手。当任一玩家在 $k$ 个游戏中的任意一个无法进行有效移动时游戏结束，无法移动的玩家输掉游戏。如果游戏持续了 $10^{100}$ 回合，则该游戏被视为平局。

现在，给定一个包含 $k$ 个图游戏的集合 $(G_1, s_1), \dots, (G_k, s_k)$，Roundgod 需要从这 $k$ 个游戏中选择一个非空子集，并与 kimoyami 在所选游戏的连接上进行对弈。Roundgod 想知道，有多少种选择非空子集的方法，使得他在双方均采取最优策略的情况下能够赢得游戏？由于答案可能很大，你需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T(1 \le T \le 5)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $k(1 \le k \le 10^6)$，表示集合中图游戏的数量。

接下来是 $k$ 个图游戏的描述。

对于第 $i(1 \le i \le k)$ 个图游戏的描述，第一行包含三个整数 $n_i, m_i, s_i(1 \le n_i, m_i \le 10^6, 1 \le s_i \le n_i)$，分别表示第 $i$ 个图游戏的顶点数、边数和源顶点。

接下来 $m_i$ 行，每行包含两个整数 $u, v(1 \le u, v \le n_i, u \neq v)$，表示第 $i$ 个图中的一条边。注意，图中可能存在重边，但不存在自环。

保证对于每个测试用例，$\sum_{i=1}^k n_i \le 2 \times 10^6$ 且 $\sum_{i=1}^k m_i \le 2 \times 10^6$。

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

样例

输入 1

2
4 3 1
1 2
1 3
3 4
3
2 2 1
1 2
2 1
2 1 1
1 2
2 1 2
1 2

输出 1

1
2

说明

在样例的第一个测试用例中，Roundgod 可以选择第一个图游戏，并通过将标记从顶点 1 移动到顶点 2 来保证获胜。

在样例的第二个测试用例中，Roundgod 可以选择第二个图游戏，并通过将标记从顶点 1 移动到顶点 2 来保证获胜；或者同时选择第一个图游戏和第二个图游戏，并通过在两个游戏中都将标记从顶点 1 移动到顶点 2 来保证获胜。