You've been tasked with helping some students learn to count in binary by converting decimal numbers into binary. To make the binary representation more readable, you've also decided to group the bits into 4-bit groups, separated by a space.

Input Specification

The first line will an integer ~N~ (~1 \le N \le 20~), the number of numbers to convert to binary. The next ~N~ lines will be a decimal integer ~i~ such that ~0 \le i \le 10^9~.

Output Specification

Output ~N~ lines where each line contains the binary representation of the number ~i~, grouped into 4-bit groups, separated by a space. If necessary, you must pad the first group to be 4 bits.

Sample Input

4
0
1
25
4095

Sample Output

0000
0001
0001 1001
1111 1111 1111