Число n называется степенным, если его можно получить из некоторого числа умножением на себя хотя бы один раз. Например 4 степенное число, так как 4 = 2 · 2, 27 тоже степенное число, так как 27 = 3 · 3 · 3, а 28 не является степенным числом. Определить, являются ли заданные числа степенными.

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

В первой строке записано количество исследуемых чисел n (1 ≤ n ≤ 10). Во второй строке записаны n исследуемых чисел, каждое из которых больше 1 и меньше 109.

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

Вывести n строк. В i-ой строке вывести YES, если i-ое число является степенным и NO иначе.