J. Mode Zero
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a binary string $$$w$$$ of odd length. As long as its length is at least $$$3$$$, you may repeatedly apply the following operation:

  • Choose any three consecutive characters of $$$w$$$.
  • Let $$$x$$$ be their mode, i.e., the character ('0' or '1') that appears at least twice among them.
  • Replace these three characters with the single character $$$x$$$.

Formally, one operation on $$$w = w_1 w_2 \ldots w_k$$$ picks an index $$$i$$$ with $$$1 \le i \le k - 2$$$, computes $$$x = \operatorname{mode}(w_i, w_{i+1}, w_{i+2})$$$, and replaces $$$w_i, w_{i+1}, w_{i+2}$$$ by the single character $$$x$$$.

We call $$$w$$$ good if some sequence of operations reduces it to the single character "0".

You are given a binary string $$$s$$$ of length $$$n$$$ and $$$q$$$ queries. Each query is a pair of integers $$$(l, r)$$$ with $$$1 \le l \le r \le n$$$, where $$$r - l + 1$$$ is odd. For each query, determine whether the substring $$$s[l..r]$$$ is good. Here, $$$s[l..r]$$$ denotes the substring $$$s_l s_{l+1} \ldots s_r$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the binary string.

The second line contains the binary string $$$s$$$ of length $$$n$$$.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$; $$$r - l + 1$$$ is odd) — a query.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each query, output "YES" if the substring $$$s[l..r]$$$ is good, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
2
9
100011011
4
1 5
5 9
4 6
3 9
5
00100
2
1 5
3 3
Output
YES
NO
NO
YES
YES
NO
Note

Consider the first test case, $$$s = \texttt{100011011}$$$. In each operation sequence below, the underlined three characters are the ones chosen for that step, and they are replaced by their mode.

The first query is $$$(1, 5)$$$, so the substring is 10001. It is good — one possible sequence of operations is: $$$$$$ \texttt{10}\underline{\texttt{001}} \to \underline{\texttt{100}} \to \texttt{0} $$$$$$

The fourth query is $$$(3, 9)$$$, so the substring is 0011011. It is good — one possible sequence of operations is: $$$$$$ \texttt{00}\underline{\texttt{110}}\texttt{11} \to \texttt{00}\underline{\texttt{111}} \to \underline{\texttt{001}} \to \texttt{0} $$$$$$