上海高校程序设计邀请赛(华东理工大学专场)

B. Next K Permutation

单点时限: 2.0 sec

内存限制: 256 MB

$n$ 个数有 $n!$ 种全排列情况,对所有排列排序后求第 $L$ 个到第 $R$ 个排列中逆序对数量之和。

逆序对定义(摘自 wiki):

设 $A$ 为一个有 $n$ 个数字的有序集 $(n>1)$,其中所有数字各不相同。
如果存在正整数 $i, j$ 使得 $1 \leq i \lt j \leq n$ 而且 $A_i \gt A_j$,则 $(A_i, A_j)$ 这一个有序对称为 $A$ 的一个逆序对,也称作逆序。逆序对的数量称作逆序数。

输入格式

第一行 case 数量 $T$。

接下来每一行有 3 个数,$n, L, R$ $(3 \leq n \leq 12, 1 \leq L \leq R \leq 10^9)$。

输出格式

输出逆序对总数。

样例

Input
3
3 3 5
6 720 720
8 14625 17743
Output
5
15
38745

提示

样例 1 说明:

$3$ 个数所有排列排序后及其逆序对个数:

  • $(1, 2, 3)$: $0$;
  • $(1, 3, 2)$: $1$;
  • $(2, 1, 3)$: $1$;
  • $(2, 3, 1)$: $2$;
  • $(3, 1, 2)$: $2$;
  • $(3, 2, 1)$: $3$.

第 3 个到第 5 个排列逆序对数量之和为 $1 + 2 + 2 = 5$。