퍼레이드

축제의 도시에는 교차로 $n$개와 양방향 도로 $n-1$개가 있고, 각 도로는 교차로 두 개를 잇는다. 어느 두 교차로 사이에도 도로를 따라가는 경로가 정확히 하나 있다. 한 교차로에 연결된 도로는 10개를 넘지 않는다.

매년 9월 13일, 곧 그 해의 256번째 날에는 도시 곳곳에서 행사가 열린다. 특히 시민들은 퍼레이드 $m$개를 계획했다. $i$번 퍼레이드는 교차로 $u_i$에서 출발해 $v_i$에서 끝나며, 두 교차로를 잇는 유일한 경로를 그대로 따라간다.

시장은 안전을 위해 도로 하나를 퍼레이드 두 개가 함께 쓰지 못하도록 정했다. 교차로는 함께 써도 되고, 출발점이나 도착점이 같아도 된다.

이 규칙을 지키면서 계획된 퍼레이드 중 최대 몇 개를 열 수 있는지 구하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음 형식으로 이어진다.

첫째 줄에 교차로의 개수 $n$이 주어진다 ($2 \le n \le 1000$). 다음 $n-1$개 줄에는 정수 $a$, $b$가 주어지며, 교차로 $a$와 $b$가 도로 하나로 이어져 있다는 뜻이다 ($1 \le a, b \le n$, $a \ne b$). 한 교차로에서 나가는 도로는 10개 이하이다. 다음 줄에 계획된 퍼레이드의 개수 $m$이 주어진다 ($0 \le m \le n(n+1)/2$).

다음 $m$개 줄에는 정수 $u_i$, $v_i$가 주어지며, $i$번 퍼레이드가 교차로 $u_i$에서 출발해 $v_i$에서 끝난다는 뜻이다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). 출발점과 도착점이 모두 같은 퍼레이드는 두 개 이상 주어지지 않는다.

각 테스트 케이스마다 도로를 두 번 이상 쓰지 않으면서 열 수 있는 퍼레이드의 최대 개수를 한 줄에 출력한다.