BYTESE2 - The Great Ball


The Great Ball (5 points) Hogwarts has organized The Great Ball to welcome the schools participating in the Triwizard Tournament. The ball is being held in the Great Hall and The Weird Sisters have been called to play the band. The students drift in to dance and then go out when they get tired. Hagrid is stationed at the gate and is noting down the time at which people enter and leave the hall. At the end of the day, he wonders what the maximum number of dancers was during the course of the ball. For convenience, he writes down for each person entering, the number of minutes from the start of the ball at which the person entered and left. The door of the hall is narrow, so at any time, either one person can enter or one person can exit, but not both. For example, suppose the observations noted down by Hagrid are the following:

Serial NoEnters atLeaves at
117
224
369
438
5510
Each line denotes the entry time and exit time of one person. (The identity of the person is not important - the same person may enter and leave many times. For instance, in the example, it might well be that the entries and exits recorded at serial no. 2 & 5 refer to the same person). In this example, the maximum size of the dancers during the ball was 4. This was achieved between time 6 & 7. Hagrid is not good at Math so he requires your help. Your task is to read the list of entry and exit times and compute the maximum number of dancers during the ball.

Input

The first line is a single integer, T (1<=T<=100), which is the number of test cases. For each of the test case, the first line contains a single integer N, (1<=N<=100), the number of entries and exits recorded. This is followed by N lines. Each of these lines consists of two integers, separated by a space, describing the entry and exit time of that person. The entry and exit times are guaranteed to be distinct, and the entry time will be less than the exit time. The constraint on entry and exit times is 10000000.

Output

A total of T lines each of them containing a single integer, denoting the maximum number of dancers during the ball.

Example

Input:
1
5
1 7
2 4
6 9
3 8
5 10

Output:
4

hide comments
bloodgreed99: 2019-03-07 12:01:37

Too easy with priority queue

yaseenmollik: 2018-11-15 22:23:39

Could have used Segment tree. But, it is much more easier to solve just using a vector..

masterchef2209: 2018-10-25 14:14:46

AC in one go...


[SPOILER]
Just create a vector of pair<int,char> and push entry time as {number,'e'} and exit time as {number,'l'} sort it and iterate once and keep count and max_value(answer) which is just a simulation of the given problem.

faiazamin_040: 2018-10-25 02:42:55

Easy. Just used three arrays.o(n^2).

anirudnits: 2018-10-17 07:49:09

don't trust spojtoolkit for this one.A nice problem :)

dheerajdheeru: 2018-07-18 14:28:24

AC in one go using hashing

adityad1998: 2018-06-25 15:57:58

Got 4 WA's just because i forgot to add "\n" -_-
Easy with array and two pointer method.

Last edit: 2018-06-25 15:58:10
ankit1cool: 2018-06-13 13:16:48

Easy using two pointer

Last edit: 2018-06-13 16:24:29
vib_s02: 2018-05-27 11:16:45

used map..

karthik_vg: 2018-03-11 15:39:28

finally found my flaw in algol :D


Added by:Paritosh Aggarwal
Date:2009-02-21
Time limit:0.282s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST WHITESPACE