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.