有n位阶梯进制，当n=4时，有：
1={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&0&0&1\\
\end{pmatrix}}\qquad
2={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&0&1&0\\
\end{pmatrix}}\qquad
3={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&0&1&1\\
\end{pmatrix}}\\
4={\begin{pmatrix}
0\\
0&0\\
0&0&1\\
0&0&1&0\\
\end{pmatrix}}\qquad
5={\begin{pmatrix}
0\\
0&0\\
0&0&1\\
0&0&1&1\\
\end{pmatrix}}\qquad
6={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&1&0&0\\
\end{pmatrix}}\\
18={\begin{pmatrix}
0\\
0&1\\
0&1&0\\
0&1&0&0\\
\end{pmatrix}}\\
\,\,\,\quad\quad\quad\quad{\color{red} 4}\quad{\color{red} 3}\quad{\color{red} 2}\quad{\color{red} 1}\quad\it{\color{red} {第i\,阶}}
阶梯进制的由来：
众所周知，小包包是个帅哥，并且十分追求完美，是个完美主义者。他善于思考，并且想把一切不美好的事物变得更加美好。大家都知道，一个十进制数转换成n位二进制数将变成一串长度为n的01串，例如当n=8时，有：
(2)_{10}=(00000010)_2\\
(127)_{10}=(01111111)_2
小包包很早以前就觉得一长串0和1太不美观，一直希望能改变它，希望寄予天天向上的积极思想，因此小包包创造了一个由0和1组成的阶梯进制，它由n阶组成（由1阶到n阶逐级上升）。它遵循以下几条规则：
1. 当第1阶为0，该数加1时，第1阶置为1。
2. 每当第i（i\geq 2）阶的低阶（即第i-1阶）全为1，第i-1阶再获得1时，第i-1阶所有的1会置为0，并会向第i阶进1。
3. 所有1下方不会有0。（因为小包包认为该进制数寓意着人生，从低阶一步步加油努力，每一阶代表人生的一个阶段，因为踏踏实实走好每一步，所以基础很牢固，1就象征着那份努力，同学们也要像小包包一样好好学习呀！）
据说将若干个十进制数转换成该阶梯进制，就能获得小包包的嘉奖，来挑战一下吧！
多组输入。
每组输入n和m。(1\leq n\leq 18, 1\leq m\leq 1000)
接下来m行，每行有一个十进制数a。(0\leq a\leq2^{63}-1)