To improve Rikka's math, Yuta designs a simple game which requires a lot of calculating. The game has several steps:
1. At first, the terminal chooses n points with integer coordinates in the two-dimensional Cartesian coordinate system and an integer K. And then, the terminal shows them to Rikka.
2. Rikka needs to color the n points using K different colors. Different points may have the same color, and some colors may not be used.
3. Rikka needs to count the number of different colorings.

Two colorings c₁,c₂ are the same if and only if there are some point o(may have real value coordinates) and angle which satisfies if we rotate the n points in c₁ degrees counterclockwise with the center o, the result will look exactly the same (including colors and positions) as c₂.

For example, when the points are (1,0),(0,1) and K is 2, coloring c₁=(1,2) and c₂=(2,1) are the same, because if we rotate the points in c₁ 180 degrees counterclockwise with the center , the result will be exactly the same as c₂. And in this case, there are 3 different colorings: (1,1),(1,2),(2,2).

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

For each testcase, the first line contains two integers n,K(1 ≤ n ≤ 3000, 1 ≤ K ≤ 109).

Then n lines follow, each line contains two integers (xi,yi)(|xi|,|yi| ≤ 108), describe the points in P.

The input guarantees that no two points have the same coordinates, i.e., , (xi,yi) ≠ (xj,yj)

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

2
2 2
1 0
0 1
5 3
0 0
2 0
0 2
2 2
1 1

7
747

In C++, please use "new int[10000000]" to declare big arrays.