#1032. 1-03G. JM的毒瘤题

回文串是一种“对称”的字符串，若字符串 $s$ 是一个回文串，则 $s$ 满足 $s = reverse(s)$ ，其中 $reverse(s)$ 表示字符串 $s$ 的翻转。

cyy非常喜欢回文串，今天他掏出了一个构造回文串的算法：

1. 在第 $1$ 步，字符串为 $p_1 = c_1$。

2. 在第 $k$ 步，字符串为 $p_k = p_{k-1} + c_k + p_{k-1}$ ，其中 $+$ 表示字符串之间的连接。

上述算法中的 $c_i$ 表示一个未知字符，这样的字符一共有 $k$ 种，分别为 $c_1, c_2, ..., c_k$ 。

就在cyy开心地构造着回文串时，毒瘤的JM想起了最长公共子串问题，和这个回文串结合了一下，弄出了一道毒瘤（其实并不）题：

为便于描述，规定 $s[l,\ r]$ 表示 $s$ 的子串 $s_{l}s_{l+1}...s_{r}$ ，其中 $s_i$ 表示 $s$ 的第 $i$ 个字符，且 $i \in [1,\ |s|]$，其中 $|s|$ 表示 $s$ 的长度。例如 $s =$ abcde，则 $s[2,\ 3] =$ bc。

给定 $q$ 次询问，每次给定五个正整数 $k,\ l_1,\ r_1,\ l_2,\ r_2$ ，求 $p_k$ 的两个子串 $p_k[l_1,\ r_1]$ 和 $p_k[l_2,\ r_2]$ 的最长公共子串的长度是多少。

例如 $k = 3$ ，则 $p_3 =$ abacaba，那么：

$p_3[1,\ 2]$ 和 $p_3[4,\ 5]$ 的最长公共子串为a，其长度为 $1$ ；

$p_3[1,\ 4]$ 和 $p_3[3,\ 6]$ 的最长公共子串为ab或ac，其长度为 $2$ 。

第一行一个正整数 $q$ ，表示询问次数。

接下来 $q$ 行，每行五个正整数 $k,\ l_1,\ r_1,\ l_2,\ r_2$ ，表示一次询问。

对于每次询问，输出一行一个非负整数表示答案。

样例输入

3
3 1 2 4 5
3 1 4 3 6
3 1 1 2 2

样例输出

1
2
0

$1 \le q \le 10^5$

$1 \le k \le 30$

$1 \le l_i \le r_i \le 2^k - 1,\ i \in [1,\ 2]$