Cистема числення для щастя

Обмеження: 2 сек., 256 МіБ

У Зеника є число $n$. Звісно, він буде дуже щасливий, якщо це число буде щасливим. Нагадаємо, що щасливим уважається число, у якому всі цифри — 4 або 7.

Зеник зрозумів, що його число може бути не щасливим у системі числення 10, а тому він хоче знайти основу системи числення $x$, у якій число $n$ буде щасливим, тобто в кожному розряді буде або 4, або 7.

Допоможіть Зенику знайти будь-яку основу системи числення або вкажіть, що такої не існує.

Вхідні дані

У першому рядку задано ціле число $t$ — кількість чисел $n$, для яких потрібно сказати відповідь.

У наступних $t$ рядках задано по одному цілому числу $n$ — числа, для яких потрібно знайти основу системи числення.

Вихідні дані

Для кожного $n$ у єдиному рядку виведіть ціле число — основу системи числення $x$ ($x \le 10^9$), яка підходить, або -1, якщо такої не існує.

Можна показати, що якщо відповідь існує, то існує відповідь, що не перевищує $10^9$.

Обмеження

$1 \le t \le 100$,

$1 \le n \le 10^9$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 43 1 7474477	9 -1 10