小O和小I一直喜欢打 UOJ 的比赛，然而等了半个丁酉年却也没能等到下一次比赛。眼看着 NOI 即将到来，他们决定一探究竟，找出 UOJ 沉寂的真正原因！

终于有一天，他们得知 UOJ 的管理层全都被两个一心想摧毁 OI 界的大魔王——滴滴诶柳和不响公座给封印起来。

这两个大魔王向来战略上联手对敌，战术上分工合作。每次滴滴诶柳首先给 oier 带来一堆麻烦；接着不响公座用超声波对 oier 进行催眠，降低 oier 们的反抗效率；关键时候滴滴诶柳又进行反向催眠，让 oier 拼命反击筋疲力尽。两个魔王轮流值班，有着充足的休息时间，而他们的对手却受到无间断攻击。最后随着时间的推移，oier 们的体力到了最低点时，不响公座放出大招，将 oier 封印起来。

要想拯救 UOJ，必须打败这两个魔王。小O和小I查阅资料，终于找到了获胜的方法——OI 阵。

首先，他们需要召集 $n$ 名 oier 布阵，联手对敌。为了高效地反击滴滴诶柳，他们决定让 $n$ 名 oier 站成一张图的样子，每个 oier 负责应对自己和相邻 oier 所受到的攻击。当一个 oier 受到攻击时，图中相邻的 oier 及时支援。

同时他们意识到，当一个 oier 身边有同校的 oier 时，不响公座攻击的时候他们会聊起天来从而阵法被破；而反之，如果身边的人都不熟悉，则会产生表现欲，有效抗住不响公座的超声波攻击。因此他们要求，图中任意两个相邻的 oier 来自不同的学校。

现在已知这张图的构成。该图具有 $n$ 个点 $m$ 条边，节点编号依次为 $1,\dots ,n$。同时共有 $k$ 个学校，由于拯救 UOJ 人人有责，故每个学校都有无数的 oier 愿意出力。

小O想要知道有多少种布阵方式，但是鉴于小I最多只能数到 $5$（他学会的最大的数字来自于“一二三四五上山打老虎”），因此小O决定输出方案数模 6。

两个布阵方式被认为是不同的当且仅当存在一个节点 $i$ 使得这两种布阵方式中守卫该节点的 oier 来自不同的学校。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行三个整数 $n,m,k$，分别表示图的点数、边数、总共的学校数。

接下来 $m$行，每行两个整数 $a,b$，表示 $a,b$ 间有一条边。保证 $1\le a,b\le n$ 且 $a\ne b$。

输出格式

对于每组数据，输出一个数表示该组数据的答案。

样例

input

2
5 4 5
1 2
1 3
1 4
1 5
8 7 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

output

2
2

explanation

对于第一个数据，五个点形成一个十字路口，根据乘法原理共有 $5\times 4\times 4\times 4\times 4=1280$ 种布阵法，模 $6$ 余 $2$。

对于第二个数据，构成一个 $8$ 个点的链，当第一个点定好了之后，剩下的全都连锁反应的定好了

限制与约定

对全部数据，有 $1\le T\le 5,1\le n\le {10}^5,0\le m\le 2\times {10}^5,1\le k\le 10000$。图保证无自环。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载