#1089. Regular Bracket Sequence

一个美丽的二进制矩阵是指在其边缘上为 1，而在内部为 0 的矩阵。

今天，樱子在玩一个有趣的游戏，她手中有一个漂亮的二进制矩阵，矩阵的大小是 。她将这个矩阵转化成了一个二进制字符串 ，规则是：将矩阵的每一行按顺序依次写下，直到第 行结束。也就是说，矩阵中的第 行第 列的元素，恰好对应着字符串 中第 个字符。

现在，樱子开始好奇，这个字符串 能否是由一个“正方形”的漂亮二进制矩阵得到的。换句话说，她想知道，是否可以从一个形状为 （即行数和列数相同）的漂亮二进制矩阵构建出这个字符串 。

你需要判断，给定的二进制字符串 是否能够由一个正方形的漂亮二进制矩阵构建而来。也就是说，检查字符串 的长度是否恰好是某个正整数的平方，如果是的话，那么它就有可能来自一个正方形的矩阵。

• 第一行包含一个整数 ，表示测试用例的数量。
• 每个测试用例包含一个整数 表示字符串 的长度，下一行为一个字符串 ，表示需要判断的括号序列。

对于每个测试用例，如果 是合法的括号序列，输出 YES；否则输出 NO。

输入

5
2
11
4
1111
9
111101111
9
111111111
12
111110011111

输出

No
Yes
Yes
No
No

• 对于所有的数据，，。
• 保证所有测试用例中 的总和不超过 。