Bạn hãy giúp Kiên đếm số lượng đồ thị có ~N~ đỉnh đánh số từ ~1~ tới ~N~, ~M~ cạnh và thỏa mãn các điều kiện sau:

• Không có cạnh nối giữa một đỉnh tới chính nó
• Bậc mỗi đỉnh trong đồ thị không vượt quá 2
• Thành phần liên thông chứa nhiều đỉnh nhất có đúng ~L~ đỉnh

Input

Input gồm một dòng duy nhất chứa ba số nguyên dương ~N, M, L~ ~(2 \leq N \leq 300, 1 \leq M, L \leq N)~.

Output

In ra một số nguyên duy nhất là số lượng đồ thị thỏa mãn modulo ~10^{9} + 7~

Sample Input 1

1 1 1

Sample Output 1

0

Sample Input 2

3 1 2

Sample Output 2

3

Sample Input 3

4 3 2

Sample Output 3

6

Kiên có một đồ thị vô hướng gồm ~N~ đỉnh đánh số từ ~1~ tới ~N~ và ~M~ cạnh đánh số từ ~1~ đến ~M~. Cạnh thứ ~i~ kết nối hai đỉnh ~a_i~ và ~b_i~.

Một đồ thị được gọi là đẹp nếu nó thỏa mãn những điều kiện sau:

• Không có cạnh nối giữa một đỉnh tới chính nó
• Có nhiều nhất một cạnh nối giữa hai đỉnh bất kỳ
• Đỉnh ~1~ và đỉnh ~N~ không liên thông.

Kiên rủ Thế chơi một trò chơi trên đồ thị của mình. Hai người chơi sẽ thay phiên nhau thực hiện nước đi của mình và Kiên là người đi trước.

• Trong một nước đi, ngưới tới lượt chơi sẽ chọn hai đỉnh ~u~ và ~v~, sau đó thêm cạnh nối hai chiều giữa hai đỉnh này vào đồ thị

Người chơi đầu tiên thực hiện nước đi khi khiến cho đồ thị không còn đẹp là người thua cuộc. Bạn hãy giúp Kiên và Thế xác định người chiến thắng nếu cả hai người đều chơi tối ưu.

Input

Dòng đầu tiên gồm một số nguyên dương ~T (1 \leq T \leq 10^{5})~ là số bộ dữ liệu trong input.

Trong mỗi bộ dữ liệu có:

• Dòng đầu tiên gồm hai số nguyên ~N (1 \leq N \leq 10^{5})~ và ~M (1 \leq M \leq min(N \cdot (N-1) / 2, 10^{5}))~
• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i~ và ~b_i (1 \leq a_i, b_i \leq N)~ biểu diễn một cạnh có sẵn trong đồ thị của Kiên

Tổng của ~N~ và ~M~ trong tất cả các test không vượt quá ~2 \cdot 10^{5}~.

Output

In ra ~T~ dòng tương ứng với ~T~ bộ dữ liệu. Nếu Kiên thắng trò chơi in ra "Kien", ngược lại Thế thắng thì in ra "The".

Sample Input

4
3 0
6 2
1 2
2 3
2 0
15 10
12 14
8 3
10 1
14 6
12 6
1 9
13 1
2 5
3 9
7 2

Sample Output

Kien
The
The
Kien

Kiên có một xâu ~S~ độ dài ~N~ gồm các ký tự in thường. Kiên rất thích chữ ~K~ nên Kiên sẽ thực hiện biến đổi xâu ~S~ đúng ~K~ lần. Tại mỗi bước biến đổi Kiên thực hiện như sau:

• Gọi ~X~ là xâu đảo ngược của xâu ~S~, ~Y=S+X~
• Chọn một xâu con ~Z~ độ dài ~N~ của ~Y~ và gán ~S=Z~

Trong tất cả các cách biến đổi để đạt được xâu ~S~ cuối cùng, hãy giúp Kiên tìm được xâu có thứ tự từ điển nhỏ nhất.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N (1 \leq N \leq 5000)~ và ~K (1 \leq K \leq 10^{9})~. Dòng thứ hai chứa xâu ~S~

Output

In ra một dòng duy nhất chứa xâu có thứ tự từ điển nhỏ nhất có thể biến đổi được từ ~S~ sau đúng ~K~ bước.

Sample Input 1

5 2
abcba

Sample Output 1

aaaab

Sample Input 2

5 3
acacc

Sample Output 2

aaaac