Problem Description

众所周知，度度熊喜欢图，尤其是联通的图。

今天，它在图上又玩出了新花样，新高度。有一张无重边的无向图， 求有多少个边集，使得删掉边集里的边后，图里恰好有$K$个连通块。

Input

第一行为$T$，表示输入数据组数。

对于每组数据，第一行三个整数$N, M, K$，表示$N$个点$M$条边的图。
接下来M行每行两个整数$a,b$，表示点$a$和点$b$之间有一条边。

$1\leq T\leq 20$

$1 \leq K \leq N \leq 14$

$0 \leq M \leq N * (N + 1) / 2$
$1 \leq a, b \leq N$

Output

对第$i$组数据，输出

Case #i:

然后输出一行，仅包含一个整数，表示方法种数（对 $1\ 000\ 000\ 009$ 取模） 。

3
1 0 1
1 1 1
1 1
3 3 2
1 2
2 3
1 3

Case #1:
1
Case #2:
2
Case #3:
3