https://vjudge.net/problem/HDU-6959

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC target("avx")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-fwhole-program")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-fstrict-overflow")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("-fcse-skip-blocks")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")
int n, m, block;
struct node
{
	int lt, rt, id, lx, rx;
	bool operator<(const node &b)const
	{
		if(lx/block!=b.lx/block)return lx<b.lx;
		if((lx/block)&1)
		{
			return rx<b.rx;
		}
		else
		{
			return rx>b.rx;
		}
	}
}a[200005];
int sum, cnt[300005], A[200005], tree[200005];
int ans[200005];
int lowbit(int x)
{
	return x&(-x);
}
int query(int x)
{
	int ret=0;
	while(x)
	{
		ret+=tree[x];
		x-=lowbit(x);
	}
	return ret;
}
void update(int x, int val)
{
	while(x<100005)
	{
		tree[x]+=val;
		x+=lowbit(x);
	}
}
void update_in(int x)
{
	if(!cnt[x])
	{
		update(x,1);
	}
	cnt[x]++;
}
void update_out(int x)
{
	--cnt[x];
	if(!cnt[x])
	{
		update(x,-1);
	}
}
//long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void solve()
{
	cin>>n>>m;
	block=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
		++A[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].lx>>a[i].lt>>a[i].rx>>a[i].rt;
		++a[i].lt,++a[i].rt;
		a[i].id=i;
	}
	sort(a+1,a+m+1);
	for(int i=1,L=1,R=0;i<=m;i++)
	{
		while(L>a[i].lt)update_in(A[--L]);
		while(R<a[i].rt)update_in(A[++R]);
		while(L<a[i].lt)update_out(A[L++]);
		while(R>a[i].rt)update_out(A[R--]);
		ans[a[i].id]=query(a[i].rt)-query(a[i].lt-1);
	}	
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	for(cin>>t;t;t--)
	{	
		for(int i=1;i<=100000;i++)tree[i]=cnt[i]=0;
		solve();
	}
}