CF2264D Dr. Agos's Dark Mode

Someone has chopped up Dr. Agos's chickens. Furious, he turns to the one thing that still brings him comfort: his OLED screen. Today, he wants almost all of it black. The screen has a single row of $ n $ pixels. Its pattern is represented by a binary string $ s $ ; $ s_i = 0 $ means that the $ i $ -th pixel is dark, and $ s_i = 1 $ means that it is lit. Dr. Agos finds a contiguous segment of pixels irritating if, when read from left to right as a binary integer, its value is divisible by $ 3 $ . More precisely, the segment from position $ l $ to position $ r $ ( $ 1 \le l \le r \le n $ ) has value $$ \sum_{i=l}^{r} s_i \cdot 2^{r-i}. $$ Leading zeroes are allowed. A segment consisting only of dark pixels has value $ 0 $ , which is also divisible by $ 3 $ . Let $ f(s) $ be the number of irritating segments. Segments with different pairs of endpoints $ (l,r) $ are counted separately, even if their pixel patterns are identical. Dr. Agos wants a pattern with at most three lit pixels that minimizes $ f(s) $ among all binary strings of length $ n $ , including strings with more than three ones. Help him construct such a pattern. We can show that an answer always exists.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of pixels in the row. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print a binary string $ s $ of length $ n $ describing Dr. Agos's screen. It must contain at most three ones and minimize $ f(s) $ among all binary strings of length $ n $ . If there are multiple solutions, print any of them.

For $ n=1 $ , Dr. Agos can light the only pixel, giving $ s=\mathtt{1} $ . The only segment has value $ 1 $ , so it is not irritating and $ f(s)=0 $ . For $ n=2 $ , he can light both pixels, giving $ s=\mathtt{11} $ . The whole row has binary value $ 3 $ and is irritating, while each individual pixel has value $ 1 $ . Thus, $ f(s)=1 $ . Every binary string of length $ 2 $ has at least one irritating segment, so this is optimal. The displayed patterns are not necessarily unique.