E. Game of Dice
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It is always fun to play with dice, here is one interesting game:

You are given n fair dice with 6 faces, the faces does not necessarily have values from 1 to 6 written on them. instead, they can have any values from 1 to 100 written on them.

Suppose you threw the n dice one after another, let us define the result of the throws as the multiplication of the numbers you get from each dice mod 109 + 7.

You task is to find how many different ways you can get the result of the dice throws equal to x.

Input

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains two integers n and x (1 ≤ n ≤ 14) (0 ≤ x < 109 + 7), where n is the number of the dice and x is the required result from the throws.

Then n lines follow, the ith line contains 6 integers fi1, fi2, ..., fi6 (1 ≤ fij ≤ 100), giving the values of ith dice's faces.

Output

For each test case, print a single line containing how many different ways you can get the result of the dice throws equal to x

Example
Input
3
3 9
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
5 6
1 2 9 9 9 9
1 2 9 9 9 9
1 3 9 9 9 9
1 3 9 9 9 9
1 6 9 9 9 9
5 999999937
100 1 1 1 1 1
100 1 1 1 1 1
100 1 1 1 1 1
100 1 1 1 1 1
100 1 1 1 1 1
Output
3
5
1