N개의 정점으로 이루어진 트리가 주어진다. 각 간선은 가중치(길이)를 가지고 있다.

루트 노드는 항상 1번 노드이다. 이때 두 노드 u, v가 주어졌을 때, 트리 상에서 두 노드 사이의 거리를 구하는 프로그램을 작성하시오.

트리에서 두 노드 사이의 거리는 두 노드를 잇는 유일한 최단 경로에 포함된 모든 간선 가중치의 합입니다.

입력

첫째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N-1개의 줄에는 트리의 연결 상태와 간선의 가중치를 나타내는 세 정수 u, v, w가 공백을 사이에 두고 주어진다. 이는 u번 노드와 v번 노드가 가중치 w인 간선으로 연결되어 있음을 의미한다. (1 ≤ w ≤ 10,000)

그다음 줄에는 질문의 개수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

다음 Q개의 줄에 걸쳐 거리를 구해야 하는 두 노드 u, v가 공백을 사이에 두고 주어진다.

출력

Q개의 줄에 걸쳐, 각 질문마다 입력으로 주어진 두 노드 사이의 거리를 출력한다.

제약 조건

1 ≤ N ≤ 100,000

1 ≤ Q ≤ 100,000

1 ≤ w ≤ 10,000

루트 노드는 1번이다.

예제 입력 1

6
1 2 2
1 3 5
2 4 1
2 5 3
3 6 8
3
4 5
4 6
1 5

예제 출력 1

4
16
5