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
jas.py: 2015-06-26 10:54:20

nice1

rk: 2015-06-18 22:17:31

so use printf and dont forget that stupid output format

Last edit: 2015-06-18 22:18:38
BRAIN: 2015-06-07 17:25:26

0.19 sec and crazy logic @@

---@@@----: 2015-06-07 16:17:08

AC after 3 TLE's.... :)

Malfple: 2015-03-30 17:55:55

was trying to use segment tree until i realize the idea is really simple. Good problem 1 TLE~

Last edit: 2015-03-30 17:56:53
Nebojsa: 2015-03-15 17:23:24

Gave so many WA's because first line of input is NOT A BLANK LINE

vishal patidar: 2015-02-22 10:44:31

first line of test is not blank line

VISHAL DEEPAK AWATHARE: 2015-02-07 05:07:42

@Lakshman I solved the problem in c++, im trying my best to make input output faster in JAVA, can you point me to some link where i can learn how to make input/output faster? my C++ soultion take time - 0.19(can the exactly same program in JAVA take the same or less time) im currently using http://ideone.com/fSroES

Last edit: 2015-02-07 05:15:09
[Lakshman]: 2015-02-06 10:04:53

@Vishal There are two AC in JAVA see this http://www.spoj.com/ranks/TULIPNUM/lang=JAVA

VISHAL DEEPAK AWATHARE: 2015-02-06 09:21:04

can anyone solve this in JAVA?im getting TLE


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