It is possible to use given tree, but my complexity is O(N*log(N)+Q*log(N)) - 0.25 sec and quite a bunch of RAM. For every node store its 1st, 2nd, 4th, 8th, 16th, ... 2^16th parent. Also store number of turns on that path and final orientation after last move (horizontal/vertical). This information is enough to calculate answers at log(N).