You are looking at the floor plan of the Summer Informatics School's new building.
You were tasked with SIS logistics,
so you really care about travel time between different locations:
it is important to know how long it would take to get from the lecture room to the canteen,
or from the gym to the server room.
The building consists of n towers, h floors each,
where the towers are labeled from 1 to n, the floors are labeled from 1 to h.
There is a passage between any two adjacent towers on every floor x.
It takes exactly one minute to walk between any two adjacent floors of a tower,
as well as between any two adjacent towers, provided that there is a passage on that floor.
It is not permitted to leave the building.
You have given k pairs of locations (ta, fa), (tb, fb):
floor fa of tower ta and floor fb of tower tb.
For each pair you need to determine the minimum walking time between these locations.
For each query print a single integer: the minimum walking time between the locations in minutes.