F. Divisible Perfection
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a digit string $$$s$$$ of length $$$n$$$ where each character is a digit from $$$1$$$ to $$$9$$$.

You need to determine if, for each pair of indices $$$1 \leq i \leq j \leq n$$$, the number formed by the contiguous substring $$$s_i s_{i+1} \cdots s_j$$$ is divisible by its length $$$(j - i + 1)$$$.

Input

The first line 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 \leq n \leq 3 \cdot 10^5$$$) — the length of the string.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of digits from $$$1$$$ to $$$9$$$.

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

Output

For each test case, output YES if every substring is divisible by its length, and NO otherwise.

Example
Input
3
3
162
2
69
1
7
Output
YES
NO
YES
Note

In the first test case, all substrings are divisible by their lengths:

  • All $$$1$$$ length substrings $$$1$$$, $$$6$$$ and $$$2$$$ are divisible by $$$1$$$.
  • All $$$2$$$ length substrings $$$16$$$ and $$$62$$$ are divisible by $$$2$$$.
  • The $$$3$$$ length substring $$$162$$$ is divisible by $$$3$$$.

So the answer is YES for this test case.

In the second test case, the substring $$$69$$$ is not divisible by its length $$$2$$$, so the answer is NO for this test case.