Dixon was in his house, he was a little bored, so he took some dominoes from the case and started thinking: “It is possible to use Qx pieces from the Dominoes so it can make a simulation of a game?” so, Dixon is not a super programmer, but he knows a little bit of constraints in the problems, so he will give it to you, your task, if you choose to accept it, is to find all the possible ways of some N pieces of Domino can be joined together to make a game simulation using exactly Qx dominoes pieces. If you can’t do this, you should print “0”

Input

The input will consists of an integer T, denoting the number of test cases, next, T cases will follow, every case starts with 2 lines N and Q, being N the number of dominoes David has and Q the number of queries you should do, then, N lines will follow, denoting the two parts of a domino piece, as you may know, the domino piece is split in two, so you can join by any side another piece, after this, Q lines will follow, denoting the number of piece you must use to build the game simulation.

Constraints

1<=T<=100

1 <= N <= 16

1 <= Q <= 16

0 <= N₁ … N_N <= 6

1 <= Q₁ … Q_N <= N

Output

You should output all the possible ways to form a game using Qx pieces (with any possible permutation too), as this number can grow very huge, we need you to print the output modulo 31337.

Example

Input:
3
4 3
2 3
3 1
1 4
4 3
1
3
4
2 1
1 2
1 2
2
2 1
1 1
1 1
2

Output:
8
10
4
4
8

Domino idea credits goes to: Daniel Ampuero and Luis Arguello

Example of the output with the first case and Q=4

• solution 1: joining the pieces 1, 2, 3 and 4.
• solution 2: joining the pieces 4, 3, 2 and 1.
• solution 3: joining the pieces 2, 3, 4 and 1.
• solution 4: joining the pieces 1, 4, 3 and 2.

Tip: In the case with one piece only, you can form a game starting with the two faces of every single piece, i.e. if we want to form a game using just the piece "2 1", one possible game is "2 1" and the other "1 2", resulting in two different ways.