내가 어디를 거쳐갔더라?

승현이가 사는 마을은 교차로 $N$개와 양방향 도로 $M$개로 이루어져 있다. 각 도로는 서로 다른 두 교차로를 잇고, 어느 두 교차로 사이든 도로를 하나 이상 지나 오갈 수 있다. 서로 다른 두 교차로를 직접 잇는 도로는 많아야 하나다. 교차로에는 주민 편의를 위해 $1$번부터 $N$번까지 번호를 붙여 두었다.

일요일에 승현이는 자기 집에서 출발해 같은 마을에 사는 친구 민수네 집에 놀러 갔다. 이사 온 지 얼마 되지 않아 도로망을 전혀 몰랐고 자기 집과 민수네 집만 겨우 알아볼 수 있었기 때문에, 한참 헤맨 끝에야 민수네 집에 도착했다. 헤매는 동안 같은 교차로를 여러 번 지나기도 했다.

승현이가 기억하는 것은 두 가지다. 출발한 뒤로는 자기 집이 있는 교차로에 다시 들르지 않았고, 민수네 집이 있는 교차로에 도착하자마자 바로 민수네 집에 들어갔다. 그러니까 승현이가 걸은 길은 자기 집 교차로에서 시작해 민수네 집 교차로에서 끝나고, 그 사이에는 두 교차로 중 어느 쪽도 지나지 않는다. 나머지 교차로는 몇 번을 지나든 상관없다.

승현이는 이 기억과 어긋나지 않는 길 가운데 적어도 하나가 지나는 교차로가 몇 개인지 궁금해졌다. 출발점인 자기 집 교차로와 도착점인 민수네 집 교차로도 지난 교차로로 센다. 지적 호기심이 많은 승현이는 여기서 한발 더 나아가, 자기 집이 $a$번 교차로에 있고 민수네 집이 $b$번 교차로에 있었다면 그 개수가 몇이었을지도 궁금해졌다.

궁금해하는 승현이를 도와줄 프로그램을 작성하자.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 1000$)가 주어진다.

각 테스트 케이스의 첫 줄에는 마을의 교차로 수 $N$ ($2 \le N \le 200000$)과 도로 수 $M$ ($1 \le M \le 500000$)이 공백으로 구분되어 주어진다. 이어지는 $M$개 줄에는 정수 $u$와 $v$ ($1 \le u, v \le N$, $u \ne v$)가 공백으로 구분되어 주어지며, $u$번 교차로와 $v$번 교차로를 직접 잇는 도로가 있다는 뜻이다. 그다음 줄에는 승현이가 궁금해한 횟수 $Q$ ($1 \le Q \le 500000$)가 주어진다. 이어지는 $Q$개 줄 가운데 $i$번째 줄에는 정수 $a_i$와 $b_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$)가 공백으로 구분되어 주어지며, 승현이네 집이 $a_i$번 교차로에, 민수네 집이 $b_i$번 교차로에 있는 경우를 묻는다는 뜻이다.

모든 테스트 케이스에서 $N$의 합은 $200000$을 넘지 않고, $M$의 합과 $Q$의 합은 각각 $500000$을 넘지 않는다.

각 테스트 케이스마다 $Q$개의 줄을 출력한다. 그중 $i$번째 줄에는 $i$번째 질문의 답, 즉 승현이네 집이 $a_i$번 교차로에 있고 민수네 집이 $b_i$번 교차로에 있을 때 승현이가 지났을 가능성이 있는 교차로의 개수를 출력한다. 서로 다른 테스트 케이스 사이에 빈 줄을 출력하면 안 된다.