Рик влюблен в Юнити. Но и мистер Мисикс также любит Юнити. Поэтому Рик и мистер Мисикс «любовные соперники».

Юнити нравится рэп, поэтому было решено, что они должны участвовать в рэп игре (баттле), чтобы выбрать лучшего. Рик слишком ботаник, поэтому вместо этого он собирается сделать свой текст используя его оригинальный алгоритм на лирике песни «Rap God».

Его алгоритм немного сложен. Он делает дерево с n вершинами, пронумерованными от 1 до n. На каждом ребре дерева написана маленькая латинская буква. Он определил str(a, b), как строку сформированную написанием всех букв, одну за другой, на кратчайшем пути от a до b (длина строки равна расстоянию от a до b). Заметьте, что str(a, b) это, записанная задом наперед, строка str(b, a). Также строка str(a, a) является пустой строкой.

Чтобы сделать лучший текст, ему необходимо отвечать на некоторые запросы, но он не ученый-компьютерщик и не может ответить на эти запросы, поэтому он просит вас помочь ему. Каждый запрос характеризуется двумя вершинами x и y (x ≠ y). Ответом на этот запрос является кол-во таких вершин z, что z ≠ x, z ≠ y и str(x, y) лексикографически больше, чем str(x, z).

Строка x  =  x₁x₂...x_|x| лексикографически больше, чем строка y  =  y₁y₂...y_|y|, если |x|  >  |y| и x₁  =  y₁,  x₂  =  y₂,  ...,  x_|y|  =  y_|y|, или существует такое r (r  <  |x|,  r  <  |y|), что x₁  =  y₁,  x₂  =  y₂,  ...,  x_r  =  y_r и x_{r  +  1}  >  y_{r  +  1}. Символы сравниваются, как их ASCII коды (или как их позиции в алфавите).

Помогите Рику заполучить девушку.