gray

Le code de Gray est une énumération de tous les mots binaires (et donc de tous les entiers) telle que pour passer d'un mot à un autre un seul bit est changé : soit on ajoute un 1 à gauche, soit on change un bit du premier mot. On appelle code de Gray de n le n-ème mot binaire de cette énumération où le code de Gray de 0 est 0. Voici les codes de Gray des entiers de 0 à 15:

0 → 0
1 → 1
2 → 11
3 → 10
4 → 110
5 → 111
6 → 101
7 → 100
8 → 1100
9 → 1101
10 → 1111
11 → 1110
12 → 1010
13 → 1011
14 → 1001
15 → 1000

Il existe de nombreuses méthodes pour calculer le code de Gray, en voici une:

• le code de Gray de 0 est 0 ;
• si n est pair, on prend le code de Gray de n-1 et on inverse le bit immédiatement à gauche du bit à 1 le plus à droite (s'il n'y a rien à gauche, on ajoute un 1 à gauche);
• si n est impair, on prend le code de Gray de n-1 et on inverse le dernier bit.

Votre objectif est de calculer le code de Gray correspondant à un entier donné en entrée (sous format décimal).

Entrée : La première ligne contient le nombre d'instances. Chaque instance est constituée d'une ligne contenant un unique entier (<10000) en décimal.

Sortie : Pour chaque instance, vous devez renvoyer une ligne contenant le code de Gray correspondant. Noter que le chiffre le plus à gauche doit être un 1.

Input

4
7
12
14
156

Télécharger l'entrée

Output

100
1010
1001
11010010

Télécharger la sortie