TULIPNUM - Tulip And Numbers

Little Tulip recently learnt about how to  write numbers. So she wrote some numbers in a paper in a line. But she never wrote a number which is less than the prevous one.

Now she want to know how many different numbers are in a given range.

In short, you are given an array of N integers indexed from 1 to N, and q queries, each in the form i j, you have to find the number of distinct integers from index i to j (inclusive).

Input

Input starts with an integer T (≤ 15), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 10^5), q (1 ≤ q ≤ 10^5). The next line contains N space separated positive integers forming the array. Each of the next q lines will contain a query which is in the form i j (1 ≤ i ≤ j ≤ N).

Output

For each test case, print the case number in a single line. Then for each query you have to print a line containing number of distinct integers from index i to j.

Example

Input:
2

5 3
1 2 2 4 5
1 2
1 5
4 5

3 1
1 1 1
1 3


Output:
Case 1:
2
4
2
Case 2:
1

Added by:Raihat Zaman Neloy
Date:2014-10-14
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2016-06-27 11:45:09
Whenever a problem setter sets a question with strict time limit, they must take care that the I/O format is not weird or at least there is no ambiguity in the I/O format. One needs to appreciate that fast input completely relies on the input format and creating troubles in that does not judge someone's coding abilities.
2016-06-13 08:28:15
"never wrote a number less than the previous one".. DP :D

Last edit: 2016-06-13 08:28:24
2016-05-27 17:20:13
my code took exact 0.2 seconds !!!!
2016-05-23 10:39:33 zany
Have we to write "Case 1:" before output or just "1" ?


2016-05-22 20:05:01 eti goel
what is expected time complexity ? my complexity is O(n+q)
2015-12-20 19:23:13
There is no blank line after 1st input..Avoid using sets or vectors in this problem,it will give TLE..
2015-10-17 23:13:00 MAYANK NARULA
Just manage time with care in this easy problem ..
2015-09-18 00:05:57 Advitiya
fast i/o AC, else 1 TLE :'(
2015-09-17 10:19:01
TLE in c++ but AC in c with same code.....!!!!
2015-07-25 22:33:32 peeyush taneja
nice ques with a good logic
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.