Please checkout week3 programs of Nptel Competative programming. Seriously they are very tough. If anyone could write a code in c++ and python3, please help. Question in below:

There is a book reading scheduled at a popular bookstore in the city. N book lovers

are expected to show up. The i-th customer comes to the show at time Si and leaves

at time Ei. At any point of time, the set of people who are present in the bookstore

bond over books, coffee, and conversation, and become friends. After the event is

done, it turns out that some precious books were missing from the store, and it looks

like there was a planned heist. So the police want to interrogate everyone who came

to the event, but unfortunately, they don’t have enough time to speak to all of them.

They are suspecting that there are X people involved in this theft. It is natural that

those X people would be friends with each other.

Now, recalling ideas that they learned in their undergraduate days, the police come

up with the following plan: they will schedule their interrogations so that for each

collection of X friends (where each pair of people in that subset are friends), there

will be at least one person who is interrogated from that subset. But to save their

time, they want to keep their total number of interrogations to a minimum. Given the

information of about how people came and went from the event, and the number X,

help them the police find the minimum number of interrogations to be scheduled.

Note: Two people are friends if they have common time at the bookstore. For

example, the person entering at time 1 and leaving at time 3 can be a friend with

another person entering at time 3 and leaving some time afterwards. But a person

leaving at time 3 cannot be a friend with another person entering at time 4.

Input

The first line of the input contains an integer T denoting the number of test cases.

The description of T test cases follows. Each test case starts with a line

containing N and X. Each of the next N lines contains, the arrival Si and the

departure Ei of an attendee.

Output

For each test case, output a single line containing the minimum number of people

that the police should interrogate.

Constraints

1 ≤ T ≤ 100

1 ≤ X ≤ N ≤ 200

1 ≤ Si ≤ Ei ≤ 109

Example

Input:

3

3 2

1 3

3 5

4 6

4 3

1 8

2 9

3 10

4 11

4 3

1 5

4 9

8 13

12 17

Output:

1

2

0

Explanation

Example case 1.

Persons 1 and 2 are friends each other. Also Persons 2 and 3 are

friends with each other. So it is enough to interrogate gangster 2 only.

Example case 2.

All of the four persons are friends with each other. The police

suspects that the size of the group is 3. So it is enough to interrogate any two of

them.

Example case 3.

There is no group of 3 persons, where each of them are friends

with each other. So the police don’t need to interrogate anybody.