Hay un árbol de \(N\) vértices con aristas con largo. En cada hoja (vértice de grado \(1\)) parte un corredor; todos corren a la misma velocidad hacia una meta \(T\) por el camino más corto, y cada uno se detiene al llegar a \(T\). El primer corredor que llega a un vértice lo reclama; si llegan varios al mismo tiempo, lo reclama el que partió de la hoja con menor número (cada corredor está en su hoja en el instante \(0\)).

Responde \(Q\) consultas: dada una hoja \(S\) y una meta \(T\), ¿cuántos vértices reclama el corredor que parte de \(S\)?

Entrada

La primera línea tiene un entero \(N\) \((2 \le N \le 10^5)\).

Cada una de las siguientes \(N - 1\) líneas tiene tres enteros \(U\), \(V\) y \(L\) \((1 \le U, V \le N,\ U \ne V,\ 1 \le L \le 10^4)\): una arista de largo \(L\) entre \(U\) y \(V\).

La siguiente línea tiene un entero \(Q\) \((1 \le Q \le 10^5)\).

Cada una de las siguientes \(Q\) líneas tiene dos enteros \(S\) y \(T\) \((1 \le S, T \le N)\); \(S\) siempre es una hoja.

Salida

Para cada consulta, en orden, una línea con la cantidad de vértices que reclama el corredor de \(S\).

Ejemplo 1

Entrada

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

Salida

3
5
1
1
1
2
1
2

Regional Latinoamericana 2024 del ICPC, problema G («Grand Glory Race»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.