Имеется бесконечное количество лампочек, находящихся в выключенном состоянии. На каждом этапе игры включаются (если они были выключены) или выключаются (если они были включены) все те лампочки, номера которых кратны номеру этапа игры.
Определить состояние n-той лампочки после n-го этапа игры.
Сначала задано количество тестов t (1 ≤ t ≤ 10). Далее следует t строк с указанием номера n (0 < n ≤ 10^5
) этапа игры.
Вывести t строк с указанием состояния соответствующей лампочки: 0 - лампочка выключена, 1 - включена.