WARush is very famous in super-coder. In super-coder algorithm contest rank-list WARush is ranked one. Now-a-days, he is doing some analysis on his rating history in super-coder algorithm contest. In super-coder an algorithm contest is said as a Single Round Tournament (SRT). After each SRT finished, rating of a contestant is updated according to his/her performance. WARush collected all this rating information, and using this he created a line chart.To make things more clear, let us consider the following table as his rating info.

From this table, we see that his first SRT was SRT-306, and rating after that SRT was 1, so he marked point (1, 1) as r₁ in graph paper, his second SRT was SRT-320 and rating after that SRT was 3, so he marked (2, 3) as r₂, then he add r₁ with r₂ by a straight line and so on.In general for his i^th SRT he marked point (i, rating after i^th SRT) by r_i. After marking all the points he will add point r_i with r_i-1 by straight lines, for all 1 < i ≤ N, Where N is the number of SRTs he participated. Look at figure 1 for more clear idea.

Fig 1: Line Chart Considering all SRTs	Fig 2: Line Chart Ignoring SRT 380

After drawing line chart, he became very interested about the number of peaks. There are two kinds of peaks in a line chart, 1) Upper Peak and 2) Lower Peak. Upper Peak is those points in a line chart, both of previous and next point of which have smaller y coordinates, and Lower Peak is those points in a line chart, both of previous and next point of which have greater y coordinates.

For example total number of peak in figure 1 is 3. Two of them are upper peaks, which are (3, 4) and (5, 5), and one of them is lower peak which is (4, 2).

WARush observed that by ignoring SRT-380, his line chart will become same as figure 2, in which number of peaks is only 1. By observing this he became more curious. Now he wants to know, by ignoring 0 or more SRTs, how many distinct line chart having K peaks can be possible. WARush called these line charts "K-peak Line charts", in a K-peak line chart he doesn't allow two consecutive points having same y coordinate.

Input starts with an integer T (≤ 12), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers N (1 ≤ N ≤ 10000) and K (0 ≤ K ≤ 50). Each of the next N lines contains two integers, SRT_i (1 ≤ SRT_i ≤ 10⁹) and Rating_i (1 ≤ Rating_i ≤ 10⁹). You can safely assume that all the SRTs are distinct.

For each case, print the case number and the number of distinct K-peak line charts modulo 2³².