시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 2 2 66.667%

## 문제

An undirected simple graph $G$ can be divided into connected components. Let $x$ be the number of trees among these components. Then the value of graph $G$ 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$ labeled vertices. Print the answer modulo $998\,244\,353$.

Note that a simple graph is an undirected graph in which both multiple edges and loops are disallowed. 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 not connected to any other vertex in the graph.

## 입력

The first line contains an integer $T \le 100$, denoting the number of test cases. Each of next $T$ lines contains two space-seperated integers $n$ and $k$ ($1 \le n \le 10^4$, $1 \le k \le 20$).

## 출력

For each test case, print a single line containing the answer.

## 예제 입력 1

2
3 1
4 2


## 예제 출력 1

12
150