An undirected simple graph G can be divided into some connected components. Let x be the number of trees among these components, graph G's value is defined as x^k.
Given n and k, your task is to calculate the sum of values of all undirected simple graphs with exactly n vertices.
Print the answer module 998244353.
*Simple graph : A simple graph is an undirected graph in which both multiple edges and loops are disallowed.
*Connected component : In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
The first line contains an integer T <= 100, denoting the number of testcases.
T lines follow. Each line contains two space-seperated integers n <= 10000 and k <= 20.
For each testcase, print a single line containing the answer.