Description

Little Red Riding Hood likes palindromic numbers, but numbers in real life are often not palindromes. Now she has $t$ numbers. She knows that each of these $t$ numbers is a palindrome in base $x$ ($x \ge 2$). For each number, find the smallest such base $x$.

Input Format

The first line contains an integer $t$ ($1 \le t \le 1000$). Each of the next $t$ lines contains a number $a_i$ ($0 \le a_i \le 10 ^ {10}$).

Output Format

Output $t$ lines. Each line contains the required $x$.

4
1
4
21
345332

2
3
2
114

Hint

$1$ in binary is $1$, and $4$ in base $3$ is $11$. $21$ in base $2$ is $1\ 0\ 1\ 0\ 1$, and $345332$ in base $114$ is $26\ 65\ 26$.

Translated by ChatGPT 5