Oyun keçidlər ilə

Sonsuz sayda lampa var və hamısı başlanğıcda söndürülmüş vəziyyətdədir. Oyunun hər mərhələsində, mərhələ nömrəsinə bölünə bilən bütün lampalar ya yandırılır (əgər söndürülübsə), ya da söndürülür (əgər yandırılıbsə).

n-ci lampanın oyunun n-ci mərhələsindən sonra hansı vəziyyətdə olduğunu müəyyən edin.

Giriş məlumatları

Birinci sətirdə testlərin sayı t (1 ≤ t ≤ 10) verilir. Sonra t sətir gəlir və hər birində oyunun mərhələ nömrəsi n (0 < n ≤ 10^5) verilir.

Çıxış məlumatları

Hər bir test üçün müvafiq lampanın vəziyyətini göstərən t sətir çıxarın: 0 - lampa söndürülüb, 1 - yandırılıb.

Nümunələr