gray

Le code de Gray est un codage binaire tel que pour passer d'un entier au suivant on ne change qu'un seul bit. 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:

Votre objectif est, étant donné un entier en décimal, de calculer le code de Gray correspondant.

INPUT

La première ligne contient le nombre de test cases. Chaque test case est constitué d'une ligne contenant un unique entier (<10000) en décimal.

OUTPUT

Pour chaque test case vous devez renvoyer une ligne contenant le code de Gray correspondant. 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

Il faut être logué pour pouvoir envoyer une soumission.