## TSPAGAIN - Travelling Salesman Again !

There are N cities numbered from 0..N-1. A salesman is located at city 0. He wishes to visit all cities exactly once and return back to city 0. There are K toll booths. Each toll booth has a certain range of functioning. The parameters for toll k are given as x_k and y_k. If the salesman travels from city i to j, he has to pay 1 dollar toll fee to each toll p having x_p >= i and y_p <= j. Calculate the cheapest way for the salesman to complete his tour.

Input :

The first line contains T the number of test cases. T test cases follow. The first line of each test case contains two space seperated integers N and K. Each of the next K lines contains 2 integers, the ith line containing x_i and y_i (0 <= x_i,y_i < N). A blank line seperates two test cases.

Output :

Output T lines, one for each test case, containing the required answer.

Sample Input :

2

3 2

2 0

0 2

3 4

1 0

2 1

0 1

1 2

Sample Output :

3

6

Constraints :

1 <= T <= 50

2 <= n <= 1000

1 <= K <= 10000

Added by: | Varun Jalan |

Date: | 2010-04-13 |

Time limit: | 0.430s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |

Resource: | own problem used for Codechef APRIL10 contest |