← 返回题目列表

Codeforces · 2008/B

B. 方形与否

中文机器翻译题面 查看原题

一个漂亮的二进制矩阵是一个边缘有 1、内部有 0 的矩阵。

四个漂亮的二进制矩阵的示例。

今天,Sakurako 正在玩一个大小为 $$$r \times c$$$ 的漂亮二进制矩阵,并通过写下矩阵的所有行(从第一行开始到第 $$$r$$$ 结束)创建了一个二进制字符串 $$$s$$$。更正式地说,矩阵中第 $$$i$$$ 行和 $$$j$$$ 列中的元素对应于字符串的第 $$$((i-1)*c+j)$$$ 元素。

您需要检查从中获得字符串 $$$s$$$ 的美丽矩阵是否可以平方。换句话说,您需要检查字符串 $$$s$$$ 是否可以从一个漂亮的方形二进制矩阵(即 $$$r=c$$$ 的矩阵)构建。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 字符串的长度。

每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。该字符串始终是写出漂亮矩阵的字符串的结果。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

如果原始矩阵可能是方阵,则打印“是”,否则打印“否”。

示例

输入 #1

5
2
11
4
1111
9
111101111
9
111111111
12
111110011111

输出 #1

No
Yes
Yes
No
No

注意

对于第二个测试用例,可以从矩阵中获得字符串 1111:

$$$1$$$$$$1$$$$$$1$$$$$$1$$$

对于第三个测试用例,可以从矩阵中获得字符串 111101111:

$$$1$$$$$$1$$$$$$1$$$$$$1$$$$$$0$$$$$$1$$$$$$1$$$$$$1$$$$$$1$$$

第四种情况没有方阵,因此可以从中获取字符串。