大中锋走在路上见到正在战术后仰的甲苯先生。因为甲苯先生帮助他解决了祖传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到点c的路径外与点a到点b的最小编号路径有相同编号和的简单路径的条数。

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

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

1
0
3
1
6
2
8
0