题目描述

小杨有一个长度为 $n$ 的正整数序列 $A$。

小杨有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨会给出 $l_i,r_i,x_i$，请你求出 $x_i$ 在 $A_{l_i}, A_{l_i+1}, \dots A_{r_i}$ 中出现的次数。

输入格式

第一行包含一个正整数 $T$，表示数据组数。

对于每组数据：第一行包含一个正整数 $n$，表示序列 $A$ 的长度。
第二行包含 $n$ 个正整数 $A_1,A_2,\dots,A_n$，表示序列 $A$。
第三行包含一个正整数 $q$，表示询问次数。接下来 $q$ 行，每行三个正整数 $l_i,r_i,x_i$，表示一组询问。

输出格式

对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。

样例

2
5
7 4 6 1 1
2
1 2 3
1 5 1
5
1 2 3 4 5
2
5 5 3
1 4 3

0
2
0
1

提示

对于全部数据，保证有 $1 \leq T\le 5$，$1 \le n,q\le 10^5$，$1 \le A_i\le 10^9$。