Random Graph is an important model in CS, and Shortest Path is a basic topic in graph theory. This problem is a simple combination of them.

Rikka wants to generate an undirected graph with n vertices. It it clearly that there are possible edges. For each edge, Rikka tosses a special coin which has the probability of to be the head side and probability of to be the tail side. If the result is the head side, Rikka adds this edge to the graph. Otherwise, she does nothing.

As a result, Rikka gets an undirected graph G. And then she chooses a vertex from all n vertices randomly with equal probability and calculates the length of the shortest path from the chosen vertex to n(the length of each edge is 1.) If the chosen vertex can not reach n, Rikka will set the answer to 10⁹.

Anyway, at last Rikka will get an integer w, it may be 10⁹, or may represent the length of some path in G. Now, Rikka wants you to calculate the expected value of . It is easy to find that the answer must be an integer.

The first line contains a single integer t(1 ≤ t ≤ 5), the number of the testcases.

For each testcase, the first line contains two integers n,p(1 ≤ n ≤ 400, 0 ≤ p ≤ 106).

For each testcase, output a single line with a single integer, the answer modulo 998244353.

5
2 1000000
2 0
4 12345
10 12345
100 12345

276262510
466613154
86698890
508893397
860797923