Palindromic Base Finder

Little Red Riding Hood loves palindromic numbers. However, many numbers in everyday life are not palindromic. She has t numbers, and for each number n, it is known that there exists some base x (\(x \ge 2\)) in which its representation is a palindrome. Your task is to determine the minimum base x for each given number such that its representation in base x is a palindrome.

The representation of a number n in base x is obtained by repeatedly dividing n by x and recording the remainders. Note that if n < x, its representation is a single digit and is trivially a palindrome.

Input and Output are described below.

inputFormat

The first line contains an integer \(t\) representing the number of test cases. Each of the following \(t\) lines contains a non-negative integer \(n\) given in base 10.

Constraints (for example): \(1 \le t \le 10^5\) and \(0 \le n \le 10^{18}\).

outputFormat

For each test case, output a single line with the minimum base \(x\) (where \(x \ge 2\)) such that the representation of \(n\) in base \(x\) is a palindrome.

sample

3
8
15
7

3
2
2