Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

K. ab ba count
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$m$$$ pairs of alphabets, $$$(a_1, b_1), \dots, (a_m, b_m)$$$.

Given a string $$$s$$$ of length $$$n$$$, we can do the following operation on it,

  • Select two indices $$$i$$$ and $$$j$$$, ($$$1 \le i, j \le n$$$), such that there exists a $$$t$$$ with $$$a_t = s_i$$$ and $$$b_t = s_j$$$.
  • Swap $$$s_i$$$ and $$$s_j$$$.

We say that two strings $$$s$$$ and $$$t$$$ are equivalent if we can transform $$$s$$$ into $$$t$$$ by repeatedly applying the operation on it.

Find the size of largest set consisting of strings of length $$$n$$$ over the first $$$k$$$ lowercase English alphabets such that no two distinct strings in the set are equivalent.

Since the size of this set can be very large, output it modulo $$$998\ 244\ 353$$$.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\leq t \leq 100$$$), the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \leq n \leq 15000$$$, $$$0 \leq m \leq k(k - 1) / 2$$$, $$$1 \leq k \leq 7$$$), the length of the strings, the pairs of characters, and the number of characters.

$$$m$$$ lines follow, the $$$t$$$-th line has 2 characters $$$a_t$$$ and $$$b_t$$$ separated by a space, denoting that we can swap those 2 characters in a string. ($$$a_t \neq b_t$$$, $$$a_t$$$ and $$$b_t$$$ are from the first $$$k$$$ lowercase English alphabets)

The summation of $$$n$$$ over all test cases does not exceed $$$15000$$$.

Output

For each test case, output the size of this largest set modulo $$$998244353$$$.

Example
Input
3
1 0 7
2 1 7
a b
3 1 2
a b
Output
7
48
4
Note

In the first test, all 7 possible strings are non-equivalent.

In the second case, out of the 49 possible strings, only the strings "$$$ab$$$" and "$$$ba$$$" are equivalent. Therefore, answer is 48.