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
2015-01-29 06:27:00 Faiz Malik
Easy 1 :) Use scanf/printf instead of cin/cout (To avoid TLE :/)
2015-01-27 04:14:04 VISHAL DEEPAK AWATHARE
im getting wa?? i tried all test cases myself and always getting correct answer? i used long values,are integers greater than this ?

Last edit: 2015-01-28 03:37:33
2015-01-02 16:18:35 OneMoreError
kudos ^_^
precomp + normal i/o
AC with .200
2014-12-30 12:12:34 Anubhav Balodhi
got tle with my logic :-/
[edit] ACed but I agree with , time limit too strict.

Last edit: 2014-12-30 12:20:18
2014-12-21 20:19:46 Mauro Persano
A .2s time limit makes no sense for an I/O-bound problem like this.
2014-12-10 17:57:37 [Lakshman]
@aky NO, I am using fast IO for my fastest solution
2014-12-10 17:34:21 aky
@[lakshman] is ur fastest soln using scanf/printf?
2014-12-10 15:54:40 [Lakshman]
@aky My AC solution did not consider any blank like just use the normal I/O like scanf/printf or cin/cout.
2014-12-10 13:48:04 aky
I'm using fgets to scan N nos. This works fine on my PC but gives SIGSEGV here. r thr additional blank lines?

Last edit: 2014-12-10 14:07:51
2014-11-11 22:07:53 Petar Nyagolov
My 20th AC :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.