Description

Xiao Ou likes strings, especially palindromic strings that contain only the two characters 0 and 1.

Xiao Ou also likes palindromes, especially strings that have some palindromic substrings, but not too many.

Xiao Ou likes construction even more, so he thinks about the following problem:

Given positive integers $n$ and $k$, with $k \le n$ guaranteed, can you construct a string $S$ of length $n$ consisting only of characters 0 and 1, such that the number of essentially different non-empty palindromic substrings of $S$ is exactly $k$?

Xiao Ou is a construction newbie and cannot beat the predecessors who have already brute-forced 100,000 or even 90,000 construction problems, so he asks you to help solve this problem, and hopes that when a solution exists, you can output any valid construction.

Some basic definitions about strings are given below. If you are very familiar with strings, you may skip this part.

• For a string $S$ of length $n$, let $S_i$ be the $i$-th character of $S$ from left to right.
• For a string $S$ of length $n$, define its substring $S[l;r]\; (1\le l\le r\le n)$ as the string formed by concatenating $S_l, S_{l+1}, \ldots, S_r$ from left to right. In particular, the empty string is also a substring of $S$.
• Two substrings $S[l_1;r_1]$ and $S[l_2;r_2]$ of $S$ are called essentially different if and only if $S[l_1;r_1] \ne S[l_2;r_2]$.
• For a string $S$ of length $n$, define its reverse string $S^{T}$ as the string formed by concatenating $S_n, S_{n-1}, \ldots, S_1$ from left to right.
• A string $S$ is a palindrome if and only if $S = S^{T}$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

One line contains two positive integers, representing $n$ and $k$ for this test case.

Output Format

For each test case:

If there is no solution, output one line with the string No.

Otherwise, output two lines. The first line is the string Yes, and the next line is a 01 string of length $n$, which is your constructed solution. If there are multiple solutions, output any one.

4
4 4
8 6
15 14
114514 1

Yes
0101
No
Yes
010100000111101
No

Hint

For the first test case, the essentially different palindromic substrings are: 1, 0, 101, 010, for a total of four.

Constraints and Notes

For $20\%$ of the testdata, $n \le 15$.
For another $10\%$ of the testdata, $k = n$.
For another $20\%$ of the testdata, $1000 \le n \le 2000$, $k \ge \left\lfloor\dfrac{n}{2}\right\rfloor + 100$.
For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le k \le n \le 2\times 10^5$.

Translated by ChatGPT 5