题号：NC219805
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
The N-ary tree is a tree that each node has exactly 
child nodes.
You are given an N-ary tree with infinite nodes, each node is numbered from 
to infinity according to the level order(from left to right, level by level).
The first 13 nodes on the 3-ary tree.
Given the number 
and 
of the two nodes, you have to calculate the lowest common ancestors(LCA) of these two nodes.
Definition of the lowest common ancestors(LCA): The LCA of two nodes on the tree refers to the node is the ancestor of these two nodes with the shortest distance to these two nodes, it should be noted that the node itself is also considered its own ancestor. For example, on the 3-ary tree the LCA of node
and node 
is node .
Definition of the lowest common ancestors(LCA): The LCA of two nodes on the tree refers to the node is the ancestor of these two nodes with the shortest distance to these two nodes, it should be noted that the node itself is also considered its own ancestor. For example, on the 3-ary tree the LCA of node
输入描述:
The first line contains an integer— the number of test cases.
Each test case contains three integersrepresenting the tree is an n-ary tree and number of two nodes.
输出描述:
For each test case output a positive integer to represent the LCA of the given two nodes.