graph

Problem Description

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.

Input

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.

Output

For each testcase, print a single line containing the answer.

Sample Input

2
3 1
4 2

Sample Output

12
150

Author

学军中学

Source

2016 Multi-University Training Contest 8