You are given an array A of integers of size N, and Q queries. For each query, you will be given a set of distinct integers S and two integers L and R that represent a range in the array. Your task is to count how many numbers in the given range are divisible by at least one number from the set.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers, N and Q (1 ≤ N, Q ≤ 105), the size of the array and the number of queries, respectively.
The next line contains N space-separated integers, the values of the array A (1 ≤ Ai ≤ 109).
Each of the next Q lines contain the description of one query in the form:
LRS
Where L and R (1 ≤ L ≤ R ≤ N) represent the range, and S is an integer between 1 and 1023 (inclusive) and represents the set; consider the binary representation of the number S, if the ith bit (1-based) is 1, then the number i belongs to the set. Since S is less than 1024, the values in the set are between 1 and 10.
For example: if S is equal to 6, the binary representation of 6 is 110, and this means the values in the set are 2 and 3.
_The input was given in this way to reduce the size of the input file._
Print the answer for each query on a single line.
## Input
The first line of input contains a single integer T, the number of test cases.The first line of each test case contains two integers, N and Q (1 ≤ N, Q ≤ 105), the size of the array and the number of queries, respectively.The next line contains N space-separated integers, the values of the array A (1 ≤ Ai ≤ 109).Each of the next Q lines contain the description of one query in the form:LRSWhere L and R (1 ≤ L ≤ R ≤ N) represent the range, and S is an integer between 1 and 1023 (inclusive) and represents the set; consider the binary representation of the number S, if the ith bit (1-based) is 1, then the number i belongs to the set. Since S is less than 1024, the values in the set are between 1 and 10.For example: if S is equal to 6, the binary representation of 6 is 110, and this means the values in the set are 2 and 3._The input was given in this way to reduce the size of the input file._
## Output
Print the answer for each query on a single line.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N, Q \in \mathbb{Z} $ denote the size of the array and number of queries.
- Let $ A = (a_1, a_2, \dots, a_N) $ be the array of integers, where $ a_i \in \mathbb{Z}^+ $.
- For each query $ q \in \{1, \dots, Q\} $:
- Let $ L_q, R_q \in \mathbb{Z} $ denote the range indices ($ 1 \le L_q \le R_q \le N $).
- Let $ S_q \in \mathbb{Z} $, $ 1 \le S_q \le 1023 $, represent a subset of $ \{1, 2, \dots, 10\} $ via its binary encoding:
$$
\text{Let } D_q = \{ i \in \{1, 2, \dots, 10\} \mid \text{the } i\text{-th bit of } S_q \text{ is } 1 \}
$$
**Constraints**
1. $ 1 \le T \le \text{unknown (but bounded by input)} $
2. $ 1 \le N, Q \le 10^5 $
3. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, N\} $
4. $ 1 \le L_q \le R_q \le N $ for all $ q \in \{1, \dots, Q\} $
5. $ 1 \le S_q \le 1023 $ for all $ q \in \{1, \dots, Q\} $, so $ D_q \subseteq \{1, 2, \dots, 10\} $
**Objective**
For each query $ q $, compute:
$$
\left| \left\{ i \in \{L_q, L_q+1, \dots, R_q\} \mid \exists d \in D_q \text{ such that } d \mid a_i \right\} \right|
$$