编程题
### 问题描述
小L同学刚学完完全二叉树，又接触到了最近最近公共祖先的知识点，小A同学给小L同学出个题目：定义完全N叉树就是每个节点有 $N$ 个子节点，按节点的深度和左右顺序编号，根节点为 1 ，假设为完全4叉树，其子节点分别是 2,3,4,5，节点 2 的子节点分别是6,7,8,9。最近公共祖先（LCA）就是两个节点离根节点距离最远的公共祖先。比如，完全4叉树中，LCA(6,9) = 2,LCA(10,17) = 1 , LCA(3,10) = 3 ;小L同学会先被给两个数 $n,m$，分别表示完全 $n$ 叉树和 $m$ 次询问，然后每次给两个数 $x,y$，求这两个点的最近公共祖先。
### 输入格式
第一行只有一个数 $t$，代表有多少次测试。
接下行包含两个整数 $n,m$，表示完全 $n$ 叉树，有 $m$ 次询问。
接下来 $m$ 行每行包括两个整数 $x,y$，求节点 $x,y$ 的最近公共祖先。
### 输出格式
每个测试输出对应 $m$ 行，每行输出答案，表示最近公共祖先节点的序号。
### 样例输入
```text
2
4 3
6 9
10 17
3 10
2 3
4 5
4 7
4 9
```
### 样例输出
```text
2
1
3
2
1
4
```
### 评测数据规模
对于 $80\%$ 的评测数据，$1\leq n \leq 100$ , $1\leq x,y \leq 10^5$。
对于 $100\%$ 的评测数据，$1\leq n \leq 1000$ , $1\leq x,y \leq 10^9$。