Є нескінченна кількість ламп, що знаходяться у вимкненому стані. На кожному етапі гри вмикаються (якщо вони були вимкнені) або вимикаються (якщо вони були увімкнені) всі ті лампи, номери яких кратні номеру етапу гри.

Визначити стан n-ої лампи після n-го етапу гри.

Вхідні дані

У першому рядку задано кількість тестів t (1 ≤ t ≤ 10). Далі йде t рядків з номером n (0 < n ≤ 105) етапу гри.

Вихідні дані

Вивести t рядків зі станами відповідних ламп: 0 - лампу вимкнено, 1 - увімкнуто.