Konfused, the Hive!

In the city of Nlogonia there is only one hive, and as in every hive there is only one queen. In this hive all bees have a single direct ancestor. Besides, everyone is the queen's child directly or indirectly.

All bees can be identified by a number and a name, and both are unique to each bee. The queen bee for example is bee number 1, and its name is the empty string. To give the number of a bee, the system is very simple, every time a new bee is born, it receives the smallest number that has not yet been used. However, bees have a peculiar naming system for their descendants. Whenever a bee has a child, its child's name is its own name concatenated with some lowercase letter. So, if a bee has a name ’aa’, the possible names for its offspring are: ’aaa’, ’aab’, ..., ’aaz’.

Now the queen bee has a list with the names of all N bees (including her own) in alphabetical order, and wants to know the answer to Q questions like: given the i and j positions in my list, how big is the biggest prefix in common between the name in position i and the name in position j.

Knowing the importance of bees to the ecosystem, you want to help answer all the queen bee's questions.

NOTE: The name of the bees in the first test case in alphabetical order is (∅, a, aa, ab, c). Therefore, between the third and fourth name we have the prefix ’a’ in common, and between the second and fifth we have no prefix in common.