공항

어느 대도시의 국제공항은 한 해 4천만 명의 승객을 처리하지만, 세계에서 가장 혼잡한 공항 가운데 하나로 악명이 높다. 그림에서 보듯이 이 공항에는 활주로가 하나뿐이어서, 활주로에는 이륙을 기다리는 항공기가 늘 붐빈다. 활주로에는 서쪽 도로 $W$와 동쪽 도로 $E$의 두 방향에서 접근할 수 있고, 항공기들은 이 두 도로에 줄지어 이륙을 기다린다.

각 시각 $t$에 도로 $W$와 $E$로 임의의 수의 항공기가 도착한다. 어떤 항공기가 시각 $t$에 한 도로에 도착하면, 같은 도로에서 자기보다 앞서 기다리고 있는 항공기의 수와 같은 순위(rank)를 받는다. 시각 $t$의 도착이 모두 끝나면 관제탑이 두 도로 중 하나를 골라, 그 도로의 맨 앞 항공기가 이륙해 활주로를 떠난다. 모든 시각의 도착 정보가 주어질 때, 항공기들이 받는 순위의 최댓값을 가장 작게 만드는 관제탑의 이륙 순서를 구하려고 한다.

예를 들어 위 표는 각 시각에 도로 $W$와 $E$로 도착하는 항공기를 나타낸다. 시각 1에 항공기 $A_1$, $A_2$, $A_3$은 각각 순위 0, 1, 2를 받고, 항공기 $B_1$, $B_2$는 각각 순위 0, 1을 받는다. 이때 관제탑은 도로 $E$의 항공기 $B_1$을 이륙시키고 $B_1$은 떠난다. 시각 2에 항공기 $B_3$, $B_4$, $B_5$는 각각 순위 1, 2, 3을 받고, 이어서 도로 $W$의 $A_1$이 이륙해 떠난다. 시각 3에 항공기 $A_4$, $A_5$는 각각 순위 2, 3을 받는다. 따라서 항공기들의 순위의 최댓값은 3이며, 이는 가능한 모든 이륙 순서에 대한 최댓값 중 가장 작은 값이다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 테스트 케이스의 첫째 줄에는 시각의 수 $n$ ($1 \le n \le 5000$)이 주어진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 두 정수 $a_i$와 $b_i$ ($0 \le a_i, b_i \le 20$)가 주어지며, 각각 시각 $i$에 도로 $W$와 도로 $E$로 도착하는 항공기의 수를 뜻한다.

각 테스트 케이스마다 한 줄에, 가능한 모든 이륙 순서에 대한 항공기 순위의 최댓값 중 최솟값을 출력한다.