We can call two numbers “similar” if their lengths are equal and we can make a number ‘’similar’’ through swapping some digits of itself. For instance, 123 is similar to 321 but 12 is not similar to 120.
A sequence can be called “similar sequence” if this sequence has only one pair of ‘’similar’’ numbers.
Now, Zero writes a series of integers and he needs you to answer his queries online. For each query, he gives you two integers l and r, which represent the two endpoints of a segment. He wants to know how many successive subsequences are “similar sequences”.
There are multiple test cases.
In the first line of every test case there are two integers n (0<n<=100000) and m (0<=m<=100000), meaning that the sequence contains n integers and m queries.
The next line contains n integers a[i] (1<=i<=n, a[i] <= 10
9), which represent the integers in the sequence.
After that, there are m lines, each line containing two integers l and r.
Zero thinks that it is too simple for him to solve this problem, so he sets a variable k. In the beginning of each test case, k = 0. For each query, he sets l = l + k and r = r - k, Zero guarantees that 0<l<=r<=n, then make k the answer of this query.
The input ends with EOF.
For each query, output an integer, and there is no blank line after each test.