题目描述

大中锋走在路上见到正在战术后仰的甲苯先生。因为甲苯先生帮助他解决了祖传 Hello word! 的代码密码，大中锋想上前打个招呼。

甲苯先生突然举起喇叭说：「大家好，我是甲苯拦你斯特，是凯岩城的首席文化大使，七十二变显神通，百般武艺样样有，感受不一样的权游文化。」

这时甲苯先生看到了大中锋，激动的拉着大中锋说：「为了筹钱去北境打异鬼，我参加了今年下半年中外合写的 stl+ 项目，我将在项目中担任线段树的主写人，但是改写不是乱写，在我写的时候，发现线段树是一个满二叉树，如果让根节点编号为 $1$，对于一个编号为 $x$ 的节点，令左孩子编号为 $2x$ ，右孩子编号为 $2x+1$ 时，现在在这个二叉树上有两个节点 $a,b$，现在我想知道节点 $a$ 到节点 $b$ 之间一条路径编号和最小为多少？你要是不会就直接给我 328，我不知道什么是暗影崛起，也不知道什么是怪盗军团。」

大中锋回答：「那不就是求一条简单路径直接算吗？」甲苯先生：「那你求这颗满二叉树中还有多少条简单路径等于这个值？不知道了吧，给我 328，我到北境打赢异鬼，回到凯岩城我就还你，我们拦你斯特，有债必偿。」

大中锋为了不给甲苯先生 328，请求作为好朋友的你写一个程序能解决甲苯先生的问题。

简单路径指的是路径上各个顶点均不重复的路径。

输入格式

第一行一个正整数 $T$，表示有 $T$ 组测试数据。

接下来 $T$ 行，每行包含 $4$ 个正整数 $d,a,b,c$。其中 $d$ 表示满二叉树的树高，$a，b $表示二叉树上的两个节点，$c$ 表示要回答甲苯先生的问题类别，$c=1$ 时，回答甲苯先生第一个问题（点 $a$ 到点 $b$ 的最小路径上的编号和），$c=2$ 时，回答甲苯先生的第二个问题，即回答除了从点 $a$ 到点 $b$ 的路径外与点 $a$ 到点 $b$ 的最小编号路径有相同编号和的简单路径的条数。

输出格式

对于每组输入，输出一行，每行包含一个正整数，表示甲苯先生问题的答案。

样例

input

8
3 1 1 1
3 1 1 2
3 1 2 1
3 1 2 2
3 2 4 1
3 2 4 2
3 1 5 1
3 1 5 2

output

1
0
3
1
6
2
8
0

对于一颗深度为 $3$ 的满二叉树，含有节点 $1,2,3,4,5,6,7$。

节点 $1$ 到 $1$ 的路径编号和为 $1$ ，且没有其他路径编号和为 $1$。 节点 $1$ 到 $2$ 的路径编号和为 $1+2=3$ ，存在路径 $3-3$ 编号和为 $3$。 节点 $2$ 到 $4$ 的路径编号和为 $2+4=6$ ，存在路径 $2-1-3$ 和路径 $6-6$ 编号和为 $6$。 节点 $1$ 到 $5$ 的路径编号和为 $1+2+5=8$ ，存在路径 $8-8$ 编号和为 $8$ ，但是节点 $8$ 的深度为 $4$ 不满足条件。

数据范围与提示

对于 $20\%$ 的数据，仅存在 $c = 1$ 的情况；

对于 $20\%$ 的数据，$d ≤ 10$；

对于 $30\%$ 的数据，$d ≤ 20$；

对于 $40\%$ 的数据，$d ≤ 25$；

对于 $50\%$ 的数据，$d ≤ 30$；

对于 $100\%$ 的数据，$T\le 10,d ≤ 50$。