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
sankalp_7: 2022-11-17 12:06:43

Time limit is very strict. So, declare arrays globally and don't use endl use "\n".

BTW: My 69th :P

Last edit: 2022-11-17 12:20:40
jdmoyle: 2021-08-20 20:03:21

this question is a waste of time.. cause many tle s only because i didnot use scanf printf

taipon12: 2020-04-07 21:08:55

"The first line of a case is a blank line".
considering this will give WA.

mortiferum: 2019-11-29 10:16:32

Remember to add the Case x: to your output!

DOT: 2018-08-22 09:44:57

Easy question. Once you make certain observations from the input being sorted, you can solve in O(1) per query.

jmr99: 2018-07-17 21:51:21

same problem here https://www.spoj.com/problems/DQUERY/
applied BIT not accepted as previously it's been accepted for DQUERY but getting TLE here
applied Brt Frs accepted .

Simes: 2018-05-17 09:02:57

I think the input may be malformed. In Pascal, I got WA with readln, and AC with read.

madhavgaba: 2017-01-02 12:53:04

1 dimensional dp and 200th came easy.....all credits @pulkitgulati:)

Last edit: 2017-01-02 12:54:38
Piyush Kumar: 2016-07-20 08:30:35

O! One of those problems where the author doesn't care if you have an optimal solution. He wants to test whether you can take input and print numbers faster -_-

ov3rk1ll: 2016-07-02 07:07:00

Use fast io
same code tle with scanf
and took only 0.08 sec with with fast io


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