Имеется правильный многоугольник. Вершины многоугольника последовательно пронумерованы числами от 1 до n. Имеется также триангуляция этого многоугольника, заданная списком из n − 3 диагоналей.

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

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

Первая строка содержит количество вершин в многоугольнике n (4 ≤ n ≤ 50 000).

Каждая из следующих n − 3 строк содержит два числа ai, bi - концы i-ой диагонали (1 ≤ ai, bi ≤ n, ai ≠ bi).

Следующая строка содержит количество запросов q (1 ≤ q ≤ 100 000).

Каждая из следующих q строк содержит два целых числа xi, yi (1 ≤ xi, yi ≤ n) - вершины i-го запроса. Гарантируется, что никакая диагональ не совпадает со стороной многоугольника и никакие две диагонали не совпадают и не пересекаются.

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

Для каждого запроса выведите в отдельной строке кратчайшее расстояние.