35457번 - 회문 2 스페셜 저지

$n$진수는 수를 $n$의 거듭제곱의 합으로 표현하는 방법이다. 예를 들어 $10$진수 $12468$은 $12468=1\times 10^4+2\times 10^3+4\times 10^2+6\times 10^1+8\times 10^0$을 이용해 수를 표현하는 방법이다. 정수 $A$를 $n$진수로 표현하는 방법은 가장 낮은 자리에 $A$를 $n$으로 나눈 나머지를 나타내는 문자를 적고 그 왼쪽에 $A$를 $n$으로 나눈 몫을 $n$진수로 나타낸 표현을 쓰면 된다. 이때 나눈 몫이 $0$이라면 더 이상 쓰지 않는다.

예를 들어 $n$진수 $\overline{a_{m}a_{m-1}a_{m-2}\dots a_{1}a_{0}}_{(n)}$는 $\overline{a_{m}a_{m-1}a_{m-2}\dots a_{1}a_{0}}_{(n)}=a_{m}\times n^{m}+a_{m-1}\times n^{m-1}+a_{m-2}\times n^{m-2}+\cdots +a_{1}\times n^1+a_0\times n^0$이다.

회문이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 예를 들면 madam, level, 12321은 회문이다. 반면에 Chung-ang, university, 54899는 회문이 아니다.

$10$진수로 표현된 양의 정수 $A$가 주어질 때, $A$를 $n$진법으로 표현했을 때 회문이 되는 $n$을 찾아보자. $n$은 $2$ 이상 $A$ 이하의 양의 정수이어야 한다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 1\, 000)$

테스트 케이스의 첫 번째 줄에 $10$진수로 표현된 양의 정수 $A$가 주어진다. $(3 \le A \le 10^{7})$

항상 조건을 만족하는 $n$이 존재한다.

테스트 케이스의 첫 번째 줄에 $A$를 $n$진수로 표현했을 때 회문이 되는 양의 정수 $n$을 출력한다. 만약 가능한 $n$값이 여러 가지라면 그중 아무거나 하나를 출력한다. $(2 \le n \le A)$