A string with length $L$ is called rich if $L \ge 3$ and there is a character which occurs in this string strictly more than $L/2$ times.
You are given a string $S$ and you should answer $Q$ queries on this string. In each query, you are given a substring $S_L, S_{L+1}, \ldots, S_R$. Consider all substrings of this substring. You have to determine whether at least one of them is rich.
-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $Q$.
- The second line contains a single string $S$ with length $N$.
- Each of the next $Q$ lines contains two space-separated integers $L$ and $R$ describing a query.
-----Output-----
For each query, print a single line containing the string "YES" if the given substring contains a rich substring or "NO" if it does not contain any rich substring.
-----Constraints-----
- $1 \le T \le 10$
- $1 \le N, Q \le 10^5$
- $1 \le L \le R \le N$
- $S$ contains only lowercase English letters
-----Example Input-----
1
10 2
helloworld
1 3
1 10
-----Example Output-----
NO
YES
def compute_rich_substr(s):
 rich = [0 for _ in range(len(s)+1)]

 for i in range(len(s) - 2):
  if (s[i] == s[i+1]) or (s[i] == s[i+2]) or (s[i+1] == s[i+2]):
   rich[i+1] = rich[i] + 1
  else:
   rich[i+1] = rich[i]

 rich[len(s) - 1] = rich[len(s)] = rich[len(s) - 2]
 return rich


t = int(input())

for _ in range(t):
 n, q = list(map(int, input().strip().split()))
 s = input()

 rich = compute_rich_substr(s)

 for _ in range(q):
  l, r = list(map(int, input().strip().split()))

  if r - l + 1 < 3:
   print("NO")
  elif rich[r - 2] - rich[l - 1] > 0:
   print("YES")
  else:
   print("NO")

def compute_rich_substr(s):
 rich = [0 for _ in range(len(s)+1)]

 for i in range(len(s) - 2):
  if (s[i] == s[i+1]) or (s[i] == s[i+2]) or (s[i+1] == s[i+2]):
   rich[i+1] = rich[i] + 1
  else:
   rich[i+1] = rich[i]

 rich[len(s) - 1] = rich[len(s)] = rich[len(s) - 2]
 return rich


t = int(input())

for _ in range(t):
 n, q = list(map(int, input().strip().split()))
 s = input()

 rich = compute_rich_substr(s)

 for _ in range(q):
  l, r = list(map(int, input().strip().split()))

  if r - l + 1 < 3:
   print("NO")
  elif rich[r - 2] - rich[l - 1] > 0:
   print("YES")
  else:
   print("NO")
