#`. XHXMMMlOPUlMFF#%/':

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

For an arbitrary binary string $t$ $^{\text{∗}}$ , let $f(t)$ be the number of non-empty subsequences $^{\text{†}}$ of $t$ that contain only $\mathtt{0}$ , and let $g(t)$ be the number of non-empty subsequences of $t$ that contain at least one $\mathtt{1}$ .

Note that for $f(t)$ and for $g(t)$ , each subsequence is counted as many times as it appears in $t$ . E.g., $f(\mathtt{000}) = 7, g(\mathtt{100}) = 4$ .

We define the oneness of the binary string $t$ to be $|f(t)-g(t)|$ , where for an arbitrary integer $z$ , $|z|$ represents the absolute value of $z$ .

You are given a positive integer $n$ . Find a binary string $s$ of length $n$ such that its oneness is as small as possible. If there are multiple strings, you can print any of them.

$^{\text{∗}}$ A binary string is a string that only consists of characters $\texttt{0}$ and $\texttt{1}$ .

$^{\text{†}}$ A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements. For example, subsequences of $\mathtt{1011101}$ are $\mathtt{0}$ , $\mathtt{1}$ , $\mathtt{11111}$ , $\mathtt{0111}$ , but not $\mathtt{000}$ nor $\mathtt{11100}$ .

Format

Input

The first line contains an integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases.

The only line of each test case contains an integer $n$ ( $1 \leq n \leq 2\cdot10^5$ ) — the length of $s$ .

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

Output

For each test case, output $s$ on a new line. If multiple answers exist, output any.

Sample

0
01
010

ShanghaiTech ACM 炸鱼杯

未参加

状态: 已结束
规则: OI
题目: 46
开始于: 2024-12-10 23:00
结束于: 2024-12-15 13:00
持续时间: 110 小时
主持人: _Arahc_
参赛人数: 112

#`. XHXMMMlOPUlMFF#%/':

XHXMMMlOPUlMFF#%/':

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

#`. XHXMMMlOPUlMFF#%/':

XHXMMMlOPUlMFF#%/':

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

还没有账户？

登录