I. Visiting Friend
time limit per test
3 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

The village where Sunghyeon lives consists of N intersections and M two-way roads. The intersections are numbered by integers from 1 to N.

Each two-way road connects two different intersections, there is a path along the roads between any two intersections. Also, for any two intersections, there is at most one road directly connecting them.

On Sunday, Sunghyeon left her house and went to play at the house of her friend Changki, who lives in the same village. Since Sunghyeon has just moved in, she doesn't know anything about the village's road network, and she can only distinguish her house and Changki's house: all other houses look the same to her. After wandering for a long time, she finally arrived at Changki's house.

Sunghyeon remembers that, after departure, she did not visit the intersection where her house was located anymore, and she immediately entered Changki's house when she reached the intersection where Changki's house was located.

Sunghyeon wondered how many intersections she might have visited when she went to play at Changki's house. In other words, out of N intersections, she wants to count such intersections V that there exists a possible path for her which visited V.

Curious Sunghyeon went a step further here, and she wondered how many different intersections she might have visited if her house was at intersection A and Changki's house was at intersection B. She wants the answer for many different pairs (A, B).

Write a program to help Sunghyeon and Changki.

Input

The first line contains an integer T, the number of test cases (1 ≤ T ≤ 1000). The test cases follow.

The first line of each test case contains two integers N and M, the number of intersections and the number of roads (2 ≤ N ≤ 200 000, 1 ≤ M ≤ 500 000).

Each of the next M lines contains two integers Ui and Vi which mean there is a two-way road between these intersections (1 ≤ Ui, Vi ≤ N, Ui ≠ Vi). There is a path along the roads between any two intersections. Also, for any two intersections, there is at most one road directly connecting them.

The next line contains an integer Q, the number of questions (1 ≤ Q ≤ 500 000).

Each of the next Q lines contains two integers Aj and Bj which mean you have to find the number of different intersections Sunghyeon might have visited if her house was at intersection Ai and Changki's house was at intersection Bi (1 ≤ Aj, Bj ≤ N, Aj ≠ Bj).

The sum of N over all test cases does not exceed 200 000. The sum of M over all test cases does not exceed 500 000. The sum of Q over all test cases does not exceed 500 000.

Output

For each test case, print Q lines. The i-th of these Q lines must contain the number of intersections Sunghyeon might have visited if her house was at intersection Ai and Changki's house was at intersection Bi.

Example
Input
1
5 5
1 2
1 3
2 4
4 5
2 5
5
1 2
1 4
2 3
2 5
3 5
Output
2
4
3
3
5