ACM 세금

피터 씨는 마법의 땅 ACM 시티에 산다. 이 도시에는 구역이 $N$개, 양방향 도로가 $N - 1$개 있다. 도로는 저마다 두 구역을 잇고 길이가 정해져 있다. 모든 구역은 서로 연결되어 있어서 피터 씨는 어떤 구역 $A$에서 어떤 구역 $B$로든 갈 수 있다.

ACM 시티에는 이동에 관한 특별한 규칙이 있다. 구역 $A$에서 구역 $B$로 가려면 그 경로에 놓인 모든 도로 길이의 중앙값만큼 세금을 내야 한다. 도로가 $N - 1$개이고 모든 구역이 연결되어 있으므로 두 구역을 잇는 경로는 하나뿐이다.

아래 그림은 구역이 6개인 ACM 시티다.

원은 구역이고 선은 두 구역을 잇는 도로다. 원 안의 숫자는 구역 번호, 선 위의 숫자는 도로의 길이다. 피터 씨가 1번 구역에서 3번 구역으로 가면 지나는 도로의 길이가 1, 5, 9이므로 세금 5달러를 낸다. 6번 구역에서 4번 구역으로 가면 지나는 도로의 길이가 1, 4, 5, 7이므로 4.5달러를 낸다.

피터 씨는 궁금한 것이 많다. 두 구역 사이를 오갈 때 내는 세금을 모두 알고 싶지만 직접 계산하기는 귀찮아서, 도시에서 가장 뛰어난 프로그래머인 당신에게 계산을 부탁했다.

중앙값은 수를 크기순으로 늘어놓았을 때 한가운데 오는 값이다. 1, 5, 7, 7, 9, 10, 16의 중앙값은 7이다. 수의 개수가 짝수이면 한가운데 두 수의 합을 2로 나눈 값이 중앙값이다. 1, 5, 7, 9, 10, 17, 28, 30의 중앙값은 $(9 + 10) / 2 = 9.5$이다.

구역이 $N$개인 ACM 시티가 주어진다. 질문마다 구역 $A$에서 구역 $B$까지 가는 경로에 놓인 도로 길이의 중앙값을 구하라.

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

각 테스트 케이스의 첫째 줄에는 구역의 수 $N$이 주어진다. ($2 \le N \le 50000$)

다음 $N - 1$개 줄에는 정수 $U_i$, $V_i$, $W_i$가 주어진다. 구역 $U_i$와 구역 $V_i$를 길이 $W_i$인 도로가 잇는다는 뜻이다. ($1 \le U_i, V_i \le N$, $U_i \ne V_i$, $1 \le W_i \le 100000$)

그다음 줄에는 질문의 수 $Q$가 주어진다. ($1 \le Q \le 100000$)

다음 $Q$개 줄에는 정수 $A_i$, $B_i$가 주어진다. 구역 $A_i$에서 구역 $B_i$로 갈 때 내야 하는 세금을 묻는 질문이다. ($1 \le A_i, B_i \le N$, $A_i \ne B_i$)

질문마다 한 줄에 하나씩, 구역 $A_i$에서 구역 $B_i$로 갈 때 내야 하는 세금을 소수점 아래 한 자리까지 출력한다.

중앙값은 언제나 정수이거나 소수점 아래가 5인 수이므로 소수점 아래 한 자리로 값을 정확히 적을 수 있다.