Fadi希望编写一个程序，帮助他赢得比赛。Fadi是一个职业骗子，他掷骰子可以得到任何期望的点数(1至6)。Fadi希望知道他至少需要掷多少次骰子才能赢得比赛。 例如，在图2.18(a)所示的棋盘中，Fadi掷3次骰子就可以赢得比赛：首先掷骰子得到点数4，到达方格5，顺着梯子爬到方格16；然后掷骰子得到点数4，到达方格20，顺着梯子爬到方格33；最后只要掷骰子得到点数3就可以赢得比赛了。

输入文件的第1行是一个整数D，代表输入文件中测试数据的个数。 每个测试数据用3行来描述。 (1) 第1行包含了3个整数N、S和L，N是棋盘的大小，S是蛇的个数，L是梯子的个数，其中0<N≤20，0<S<100，0<L<100。 (2) 第2行包含了S个整数对，每对整数描述了一条蛇的起止方格位置，第1个整数是蛇的起始位置(蛇头)，第2个整数是蛇的终止位置(蛇尾)，注意方格的序号是以1开始计起的。 (3) 第3行包含了L对整数，描述了L个梯子的信息，每对整数的第1个整数是梯子的起始位置(底部)，第2个整数是梯子的终止位置(顶部)。

对每个测试数据，输出一个整数，表示为了到达N2方格处，至少需要掷骰子的次数。