题意： 给出一个二部图，U、V分别是二部图的两个点集，其中，U中每个点会有两条边连到V中两个不同的点。
完美匹配定义为：所有点都成功匹配。
思路：已知一定是完美匹配了呀(也一定存在)，我们先把度数为一的匹配了(用拓扑把度数为一的找出来)，那么剩下的图中左右各有m个点，每个点度数都不小于2，且左边每个点度数都是2，而右侧总度数是2m，因此右侧只能是每个点度数都是2。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。
然后就完了(还是看了别人的才懂得ε=ε=ε=┏(゜ロ゜;)┛)。
/* gyt
Live up to every day */
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 6e5+;
const int maxm=+;
const ll mod = ;
const int INF = 0x3f3f3f;
const db eps = 1e-;
struct node {
ll w;
int v, next;
}edge[maxn<<];
int no, head[maxn];
int bad[maxn], deg[maxn], vis[maxn];
int n, nn;
queue<int>q;
vector<int>vtt;
ll ans, must; void init() {
no=;
memset(vis, , sizeof(vis));
memset(head, -, sizeof(head));
memset(bad, , sizeof(bad));
memset(deg, , sizeof(deg));
}
void add(int u, int v, int w) {
edge[no].v=v; edge[no].next=head[u];
edge[no].w=w; head[u]=no++;
}
ll dfs(int cur, int father) {
vtt.push_back(cur);
vis[cur] = ;
for(int k = head[cur], kk; k != -; k = edge[k].next) {
int v = edge[k].v;
if(v == father) continue;
if(bad[v] || vis[v]) continue;
vis[v] = ; vtt.push_back(v);
for(kk = head[v]; kk != -; kk = edge[kk].next) {
if(!bad[edge[kk].v] && edge[kk].w != cur)
break;
}
return dfs(edge[kk].v, v)*edge[k].w%mod;
}
return ;
}
void solve() {
init(); scanf("%d", &n);
nn=n*;
for (int i=; i<=n; i++) {
int v, w; scanf("%d%d", &v, &w);
add(i, n+v, w); add(n+v, i, w);
deg[i]++, deg[n+v]++;
scanf("%d%d", &v, &w);
add(i, n+v, w); add(n+v, i, w);
deg[i]++, deg[n+v]++;
}
must=;
while(!q.empty()) q.pop();
for (int i=; i<=n; i++) {
if (deg[n+i]==) q.push(n+i); //把度数为一的提出来
}
while(!q.empty()) {
int u=q.front(); q.pop();
bad[u]=;
for (int k=head[u]; ~k; k=edge[k].next) { //找到度数为一的点连的另一个点a
int v=edge[k].v;
if (bad[v]) continue;
must=must*edge[k].w%mod;
bad[v]=;
for (int kk=head[v]; ~kk; kk=edge[kk].next) {//把a相连的点找出来，如果减掉1还是1，说明他能匹配的也只能是一个
if (bad[edge[kk].v]) continue;if (--deg[edge[kk].v]==) {
q.push(edge[kk].v);
}
}
}
}
ans=must;
//cout<<ans<<endl;
for (int i=; i<=n; i++) {
if (vis[i]||bad[i]) continue;
ll ans1=;
for(int k = head[i], kk; k != -; k = edge[k].next) {//分别两种匹配的结果
int v=edge[k].v;
vtt.clear();
vis[v]=;
for ( kk=head[v]; ~kk; kk=edge[kk].next) {
if (!bad[edge[kk].v] && edge[kk].v!=i) break;
}
ans1=(ans1+dfs(edge[kk].v, v)*edge[k].w%mod)%mod;
// cout<<ans1<<endl;
vis[v]=;
for (int j=; j<vtt.size(); j++) {
vis[vtt[j]]=;
}
vtt.push_back(v);
}
for (int j=; j<vtt.size(); j++) {
vis[vtt[j]]=;
}
ans = ans*ans1%mod;
}
printf("%lld\n", ans);
}
int main() {
int t = ;
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &t);
while(t--)
solve();
return ;
}