E. A и B и аудитории
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

A и B готовятся к олимпиадам про программированию.

Университет, в котором учатся A и B, представляет собой множество аудиторий, соединенных между собой переходами. Всего в университете n аудиторий, соединённых n - 1 переходом таким образом, что из любой аудитории можно дойти до любой по переходам. Аудитории пронумерованы от 1 до n.

Каждый день А и B пишут контесты в некоторых аудиториях своего университета, и после каждого контеста они собираются вместе в одной аудитории и обсуждают задачи. A и B хотят, чтобы расстояния от аудитории, где они будут обсуждать задачи, до аудиторий, где они пишут контесты, были равны. Расстоянием между двумя аудиториями является количество ребер на кратчайшем пути между ними.

Так как каждый день они пишут контесты в новых аудиториях, то они попросили вас помочь им найти количество возможных аудиторий для обсуждения задач на каждый из ближайших m дней.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 105) — количество аудиторий в университете.

В следующих n - 1 строках описаны переходы. В i-й из этих строк (1 ≤ i ≤ n - 1) записаны два целых числа ai и bi (1 ≤ ai, bi ≤ n), обозначающих, что i-й переход соединяет аудитории с номерами ai и bi.

В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество запросов.

Следующие m строк описывают сами запросы. В j-й из этих строк (1 ≤ j ≤ m) записаны два целых числа xj и yj (1 ≤ xj, yj ≤ n), обозначающих, что в j-й день A будет писать контест в аудитории с номером xj, B — в аудитории с номером yj.

Выходные данные

В i-й (1 ≤ i ≤ m) строке выведите количество аудиторий, равноудаленных от аудиторий, в которых A и B пишут контест в i-й день.

Примеры
Входные данные
4
1 2
1 3
2 4
1
2 3
Выходные данные
1
Входные данные
4
1 2
2 3
2 4
2
1 2
1 3
Выходные данные
0
2
Примечание

В первом примере из условия на одинаковом расстоянии от аудиторий с номерами 2 и 3 находится только одна аудитория — аудитория с номером 1.