现在，你有一个包含 $n$ 个整数的序列，其中第 $k$ 个元素记为 $a[k]$。你需要回答 $m$ 个查询。在每个查询中，给定一个区间 $[l, r]$，你需要考虑从 $1$ 到 $10$ 的每个整数 $k$。对于每个整数 $k$，你需要计算满足条件的整数 $x$ 的个数。

如果一个整数 $x$ 与整数 $k$ 和区间 $[l, r]$ 相关联且满足以下条件，则称其为有效整数：

1. 对于从 $x$ 到 $x+k-1$ 的每个整数 $i$，在集合 $\{a[l], a[l+1], a[l+2], \dots, a[r-1], a[r]\}$ 中至少存在一个元素等于 $i$。
2. 区间 $[l, r]$ 中的序列元素不包含 $x-1$ 或 $x+k$（注：原题描述中为 $x-1$ 或 $y+1$，根据上下文逻辑应为 $x+k$）。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100000$)。 第二行包含 $n$ 个整数，表示 $a[1]$ 到 $a[n]$ ($0 \le a[i] \le 2000000000$)。 接下来的 $m$ 行，每行包含两个整数 $l$ 和 $r$，描述上述查询的区间 ($1 \le l \le r \le n$)。

输出格式

对于每个测试用例，输出 $m$ 行，对应所有查询的结果。

在每个查询中，你应该计算 $10$ 个数字，分别对应 $k$ 从 $1$ 到 $10$ 的情况。为了压缩输出，程序应将每个数字对 $10$ 取模，并按顺序输出，不加空格，组成一个长度为 $10$ 的字符串。

样例

输入 1

2
5 5
1 2 4 5 6
1 5
1 2
3 4
3 5
4 5
8 9
2 3 3 3 3 6 6 6
1 8
2 3
4 5
6 8
1 2
3 4
5 6
3 8
5 5

输出 1

0110000000
0100000000
0100000000
0010000000
0100000000
1100000000
1000000000
1000000000
1000000000
0100000000
1000000000
2000000000
2000000000
1000000000