Число n називається степеневим, якщо його можна отримати з деякого числа множенням на себе хоча б один раз. Наприклад, 4 степеневе число, оскільки 4 = 2 · 2, 27 також степеневе число, бо 27 = 3 · 3 · 3, а 28 не є степеневим числом. Визначити, чи є задані числа степеневими.

Вхідні дані

У першому рядку записано одне натуральне число n - кількість досліджуваних чисел (1 ≤ n ≤ 10). У другому рядку через пропуск записано n чисел - досліджувані числа. Кожне з них більше 1 і менше 109.

Вихідні дані

Вивести n рядків. В i-му рядку записати YES, якщо i-те число є степеневим і NO у противному випадку.