题目描述

著名的$ACM$（高级计算机制造商）公司租用了一栋大楼的一层，其形状如下图所示。

该楼层在走廊的北侧和南侧各有$200$个房间。最近，公司计划进行系统改革。改革包括在房间之间搬运大量桌子。由于走廊狭窄且所有桌子都很大，一次只能有一张桌子通过走廊。因此需要制定一个计划来提高搬运效率。经理提出了以下方案：将一张桌子从一个房间搬到另一个房间可以在$10$分钟内完成。当将桌子从房间$i$搬到房间$j$时，走廊中位于房间$i$和房间$j$前面的部分会被占用。因此，在每$10$分钟内，可以同时进行多个不共享同一段走廊的搬运任务。为了更清楚地说明这一点，经理列举了一些可以同时搬运和不能同时搬运的情况。

对于每个房间，最多只会有一张桌子被搬入或搬出。现在，经理需要找到一种方法来最小化搬运所有桌子所需的时间。你的任务是编写一个程序来解决经理的问题。

输入格式

输入包含$T$个测试用例。测试用例的数量$T$在输入文件的第一行给出。每个测试用例的第一行包含一个整数$N$（$1 \leq N \leq 200$），表示需要搬运的桌子数量。

接下来的$N$行，每行包含两个正整数$s$和$t$，表示需要将一张桌子从房间$s$搬到房间$t$（每个房间编号在$N$行中最多出现一次）。从第$3 + N$行开始，剩余的测试用例以相同的方式列出。

输出格式

输出完成所有搬运任务所需的最少时间（以分钟为单位），每个测试用例输出一行。

示例输入 1

3 
4 
10 20 
30 40 
50 60 
70 80 
2 
1 3 
2 200 
3 
10 100 
20 80 
30 50 

示例输出 1

10
20
30

来源

Taejon 2001