Группа муравьев действительно гордится тем, что они построили великолепную и большую колонию. Однако ее огромный размер стал проблемой, потому что многие муравьи не знают пути между некоторыми частями колонии. Они отчаянно нуждаются в вашей помощи!

Колония муравьев была сделана как серия из n муравейников, соединенных туннелями. Муравьи, будучи предусмотрительными, в процессе постройки последовательно нумеровали муравейники. Первый муравейник, имеющий номер 0, не нуждался ни в каком туннеле, но для каждого последующего муравейника, с 1 по n − 1, муравьи также построили один туннель, соединяющий новый муравейник с одним из существующих муравейников. Конечно, этого туннеля было достаточно, чтобы любой муравей мог отправиться в любой ранее построенный муравейник, возможно, пройдя через другие муравейники на своем пути. Поэтому они не беспокоились о создании дополнительных туннелей и продолжали строить больше муравейников.

Ваша задача - учитывая структуру колонии и набор запросов, вычислить для каждого запроса кратчайший путь между парами муравейников. Длина пути - это сумма длин всех туннелей, которые необходимо преодолеть.

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

Каждый тест состоит из нескольких строк. Первая строка содержит количество муравейников n (2 ≤ n ≤ 105) в колонии. Каждая из следующих n − 1 строк содержит два числа, описывающих туннель. Строка i (1 ≤ i ≤ n − 1) содержит Ai и Li, указывающих на то что муравейник i напрямую соединен с муравейником Ai туннелем длины Li (0 ≤ Ai ≤ i − 1 и 1 ≤ Li ≤ 109). Следующая строка содержит количество запросов q (1 ≤ q ≤ 105). Каждая из следующих q строк описывает запрос и содержит два разных числа s и t (0 ≤ s, t ≤ n − 1) - номера муравейников, между которыми следует найти расстояние.

За последним тестом находится строка из одного нуля.

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

Для каждого теста выведите одну строку с q целыми числами, каждая из которых является длиной кратчайшего пути между парой муравейников запроса. Запишите результаты для каждого запроса в том же порядке, в котором запросы были заданы во входных данных.