There are N matrixs of soilders.
Now here comes an urgent task and you want to choose M of them to complete the task.
But if more than 2 selected soldiers are in the same row or column of the same matrix they will chat to each other and the efficiency will be too low.
Of course you want to avoid low efficiency.
How many ways can you choose them?
There are several test cases. The first line of the input is an integer T (0<T<=100) indicates the number of test cases.
The first line of each test case is a line of 2 positive integers N（0<N<=20) and M （0<M<=800).
Then N lines of 2 integers, m and n (0<m,n<=20) indicate the number of row and column of each matrix.
The result may be very large so for each test case output the result module by 123456789 instead in a single line.