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