【问题描述】

初始有一个红细胞。每过一个时间单位，一个红细胞会分裂成三个红细胞和一个绿细胞，而一个绿细胞会分裂成四个绿细胞，并且呈正方形网格排列。如图所示分别是经过 0, 1, 2, 3 个时间单位后的细胞分裂与排列情况。

问：经过 n 个时间单位后，第 x 行至第 y 行一共有多少个红细胞？

多组数据。

【输入格式】

第一行一个整数 T, 表示数据组数

接下来 T 行，每行三个整数 n, x, y

【输出格式】

共 T 行，每组数据的答案占一行。

【样例输入】

4
0 1 1
2 1 4
3 4 5
18 110763 232961

【样例输出】

1
9
6
130222078

【说明】

本题不再额外提供附加样例文件。

【数据规模】

30% 的数据：$T < 10, 0 ≤ n ≤ 10, 1 ≤ x ≤ y ≤ 2^n$

60% 的数据：$T < 100, 0 ≤ n ≤ 20, 1 ≤ x ≤ y ≤ 2^n$

100% 的数据：$T < 1000, 0 ≤ n ≤ 30, 1 ≤ x ≤ y ≤ 2^n$