표지판 세우기

우리 동호회와 경쟁하는 동호회가 같은 도시에 있다. 그동안 심한 장난을 여러 번 당했으니 이번에는 되갚아 줄 차례다. 알아낸 계획은 이렇다. 참가자의 눈을 가린 채 아무도 모르는 도시로 데려가 아무 데나 내려놓고, 정해진 목표 지점을 찾아오라고 시킨다. 참가자는 도시를 헤매고 다니며 목표 지점을 찾는다.

이 놀이를 망치기로 했다. 목표 지점에 가장 먼저 도착한 사람에게 상을 주기로 되어 있어서, 참가자는 도움이 될 만한 것을 모조리 이용한다. 그러니 관공서에서 세운 것처럼 보이는 표지판을 도시 곳곳에 미리 세워 두면 참가자는 그 표지판을 따라간다. 어디에 내려놓아도 표지판만 따라가면 목표 지점에 닿도록 세워 두면 헤매는 재미가 사라진다.

표지판은 비싸고 경찰의 눈에도 잘 띄므로 개수를 최소로 줄이려 한다. 참가자가 한참 돌아가게 되어도 상관없다. 어차피 도시를 모른다.

이 도시의 교차로는 모두 십자 모양이라 참가자가 어디로 갈지 예측하기 쉽다.

• 교차로에 들어온 참가자는 들어온 길의 반대편 길로 곧장 빠져나간다.
• 표지판이 있는 교차로에 도착한 참가자는 그곳에 내려졌든 지나가는 길이든 표지판이 가리키는 한 방향으로 간다.
• 표지판이 없는 교차로에 내려진 참가자는 네 방향 중 하나를 아무렇게나 골라 출발한다.

표지판 하나는 그 교차로에 이어진 네 길 중 한 방향만 가리킨다. 목표 지점에 참가자를 내려놓는 일은 없다.

어느 교차로에 내려놓든, 처음에 어느 방향을 고르든 참가자가 목표 지점에 도착하게 하려면 표지판이 최소 몇 개 필요한지 구하라.

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

각 테스트 케이스는 다음과 같다.

• 첫 줄에 교차로의 수 $n$과 목표 지점의 번호 $g$가 공백으로 구분되어 주어진다. ($5 \le n \le 100000$, $1 \le g \le n$)
• 이어지는 $n$개의 줄 중 $i$번째 줄에 네 정수 $a$, $b$, $c$, $d$가 주어진다. ($1 \le a, b, c, d \le n$) $i$번 교차로에 $a$번 교차로 쪽에서 들어온 참가자는 $c$번 교차로 쪽으로 나가고, $c$번 쪽에서 들어오면 $a$번 쪽으로 나간다. 같은 방식으로 $b$번 쪽에서 들어오면 $d$번 쪽으로, $d$번 쪽에서 들어오면 $b$번 쪽으로 나간다.

교차로마다 서로 다른 네 교차로와 길로 이어져 있다. 길은 양방향이라서 $i$번 교차로의 목록에 $j$가 있으면 $j$번 교차로의 목록에도 $i$가 있다. 도시의 모든 교차로는 길을 따라 서로 오갈 수 있다.

각 테스트 케이스마다 필요한 표지판의 최소 개수를 한 줄에 하나씩 출력한다.