### 问题描述 假设一个 $n$ 边形 $n$ 条边为 $a_1,a_2,a_3,\cdots,a_n$，定义该 $n$ 边形的值 $v = a_1 \times a_2 \times a_3 \times \cdots \times a_n$。 定义两个 $n$ 边形不同是指至少有一条边的长度在一个 $n$ 边形中有使用而另一个 $n$ 边形没有用到，如 $n$ 边形 $(3,4,5,6)$ 和 $(3,5,4,6)$ 是两个相同的 $n$ 边形，$(3,4,5,6)$ 和 $(4,5,6,7)$ 是两个不相同的 $n$ 边形。 现在有 $t$ 和 $n$，表示 $t$ 个询问并且询问的是 $n$ 边形，每个询问给定一个区间 $[l,r]$，问有多少个 $n$ 边形（要求该 $n$ 边形自己的 $n$ 条边的长度互不相同）的值在该区间范围内。 ### 输入格式 第一行包含两个正整数 $t$、$n$，表示有 $t$ 个询问，询问的是 $n$ 边形。 接下来 $t$ 行，每行有两个空格隔开的正整数 $l$、$r$，表示询问区间 $[l,r]$。 ### 输出格式 输出共 $t$ 行，第 $i$ 行对应第 $i$ 个查询的 $n$ 边形个数。 ### 样例输入 ```text 4 3 1 10 30 50 60 200 200 400 ``` ### 样例输出 ```text 0 1 18 32 ``` ### 说明 在样例中，第二个区间 $[30,50]$ 的合法三边形（三角形）的边长为 $2$、$4$、$5$。 ### 评测数据规模 对于所有评测数据，$1\leq t \leq 10^5$，$3 \leq n < 10$，$1\leq l \leq r \leq 10^5$。