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

Определить состояние n-той лампочки после n-го этапа игры.

Входные данные

Сначала задано количество тестов t (1 ≤ t ≤ 10). Далее следует t строк с указанием номера n (0 < n ≤ 105) этапа игры.

Выходные данные

Вывести t строк с указанием состояния соответствующей лампочки: 0 - лампочка выключена, 1 - включена.