• If A is friend of B and A knows some thing(any information) then A will tell it to B.
• If A is NOT friend of B and A knows some thing(any information) then A will NOT tell it to B.
• If A knows some mistake of B and A is friend of B, A will NOT tell it to Bhoondu.
• If A knows some mistake of B and A is NOT friend of B , A will tell(complain) it to Bhoondu.

One student S out of these students(1,2,... N) has done a mistake.
And one another student K somehow came to know about S's mistake. S DON'T know who is K.
Now you have to help S to find out the maximum possible threat to him.
Threat is defined as how many students has complained about S to Bhoondu.

You are also given information about friendship of students in college.
It will be given as pairs "A B" which means A is friend of B.
Note that some information given to you may be redundant.

Input

First line will contain the number of test cases T.
For each test case the first line will contain N S and F separated by space.
Where N is the number of students, S is the student who made the mistake and
F is the number of friendship information given to you.
After this next F lines will contain two numbers A and B separated by space.
There is no empty line between different test cases.

Output

For each test case the output will be an integer in a new line, which will be the maximum threat for S in the corresponding test case.

Input Constrain:

1

Example:

Input: 3 5 1 3 1 2 3 4 3 5 6 2 3 1 2 4 5 5 6 6 1 3 1 2 1 3 5 6 Output: 3 3 2

Explanation:

In 1st test case:
If 2 will know about 1's mistake then he will not tell it to Bhoondu because he is his friend so 0 threat.
If 3 will know about 1's mistake then he will tell it to 4,5. So three people will complain to Bhoondu, so threat = 3.
Case for 4 and 5 is same as 3. So maximum threat = max(0,3,3,3) = 3.