TULIPNUM - Tulip And Numbers

no tags 

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

hide comments
pardyot: 2014-11-06 18:55:52

implementing that blank line cost me many wa , but at last i had a gr8 laugh... :P

Akhilesh Anandh: 2014-10-29 15:17:19

Time limit very strict.. had to optimize I/O methods to pass.

aayush saxena: 2014-10-29 07:25:47

My 50th AC :)
Easy One :p

Kid Algorist: 2014-10-27 18:32:04

0.03, unable to optimise time furthur, :/
Do suggest a hint or two when someone does that. Thanks. ^_^

Sumit Gulati: 2014-10-27 10:31:59

Easy Question precalculation helps in O(1) complexity

ISHANI: 2014-10-27 08:08:32

Last edit: 2014-10-27 08:30:08
Pulkit Singhal: 2014-10-24 06:50:48

Easy One :P
O(1) Query Time with Fast IO passed in 0.06 seconds

Last edit: 2014-10-24 06:51:17
fitcat: 2014-10-23 07:38:14

My AC solution assumed all numbers can be represented in 32 bits.


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