SP7782 LLCA - Largest Labeled Common Ancestor

Given a labeled complete k-ary tree, find the largest labeled common ancestor of two given nodes. In a complete k-ary tree, the node in the tree is labeled sequentially from the left most child to right most child, level by level. Largest labeled common ancestor of A and B is defined as the largest labeled node in the tree which has A and B as descendants. A node is a descendant of itself. **Be careful with your finger, the source limit is 256 bytes.**

The first line of input contains an integer T (1

For each test case, output in a line the largest labeled common ancestor node.