題目傳送門
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 1000;
const ll mod = 998244353;
int G[N],du[N],vis[N];
int tot,u,v,n,st;
ll d,ans,t1,t2;
struct Edge {
int to;
ll w;
int next;
Edge(int to_=0,ll w_=0,int next_=0):to(to_),w(w_),next(next_){}
}E[N*2];
struct node {
int u;
int flag;
};
void init() {
memset(du,0,sizeof(du));
memset(G,0,sizeof(G));
memset(vis,0,sizeof(vis));
tot = 1; ans = 1;
}
inline void addEdge(int f,int t,ll dist) {
E[tot] = Edge(t,dist,G[f]);
G[f] = tot ++;
E[tot] = Edge(f,dist,G[t]);
G[t] = tot ++;
}
void topSort() {
queue<node>Q;
for(int i=1;i<=n;i++)
if(du[i] == 1)
Q.push((node){i,0});//度為1的點進行比對
while(!Q.empty()) {
node now = Q.front();
Q.pop();
int u = now.u;
if(vis[u])
continue;
vis[u] = 1;
for(int i=G[u];i;i=E[i].next) {
int v = E[i].to;
if(vis[v])
continue;
du[v] --;
//點v的度-1,因為點u會進行比對
if(du[v] <= 1) {
if(!now.flag)ans = ans * E[i].w % mod;
Q.push((node){v,!now.flag});
}
}
}
}
void dfs(int u,int dep) {
vis[u] = 1;
bool flag = true;
for(int i=G[u];i;i=E[i].next)
{
int v = E[i].to;
if(vis[v])continue;
flag = false;
if(dep%2)
t1 = t1 * E[i].w % mod;
else
t2 = t2 * E[i].w % mod;
dfs(v, dep + 1);
}
if(flag) {
for(int i=G[u];i;i=E[i].next)
if(E[i].to == st)
{
if(dep%2)t1 = t1 * E[i].w % mod;
else t2 = t2 * E[i].w % mod;
}
}
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
init();
scanf("%d",&n);
for(int i=1;i<=n;i++) {
for(int j=0;j<2;j++) {
scanf("%d%lld",&v,&d);
v = v + n;
//v集合的點加上n防止和u集合的點有交集
du[v] ++, du[i] ++;
//記錄每個點的度
addEdge(i,v,d);
}
}
n = 2 * n;//(1-n)為u,(n+1-2n)為V
topSort();//拓撲一下,将度為1的先比對好
for(int i=1;i<=n;i++) {
if(!vis[i]) {
t1 = t2 = 1; st = i;
/*在環上間隔着取,即st為結束點也是開始點(一個環)t1,t2(兩種方案)*/
dfs(i,1);
ll tmp = (t1 + t2) % mod;
ans = ans * tmp % mod;
}
}
printf("%lld\n",ans);
}
return 0;
}