회문인 수

어떤 수를 왼쪽부터 읽어도 오른쪽부터 읽어도 같으면 그 수를 회문인 수라고 한다. 예를 들어 747은 십진법으로 쓰면 회문이다. 255는 십진법에서는 회문이 아니지만 16진법으로 쓰면 FF이므로 회문이다.

양의 정수 $N$이 주어질 때, $2 \le B \le 64$인 어떤 $B$진법으로 $N$을 표현하면 회문이 되는 경우가 있는지 판정하는 프로그램을 작성하시오. $B$진법은 한 자리에 쓸 수 있는 수의 가짓수가 $B$라는 뜻이다. 십진법이면 $B$는 10이다. $B$가 10보다 큰 진법에서는 각 자리의 값 자체를 하나의 숫자로 보고 회문인지 판정하며, 맨 앞자리에 0은 붙이지 않는다.

입력은 표준입력으로 주어진다. 첫째 줄에 테스트 데이터의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 정수 $N$이 한 줄에 하나씩 주어진다. $N$은 64 이상 1,000,000 이하이다.

출력은 표준출력을 사용한다. 각 테스트 데이터마다 한 줄에 답을 하나씩 출력한다. $2 \le B \le 64$인 어떤 $B$진법으로 표현해 회문이 되면 1을, 그런 진법이 하나도 없으면 0을 출력한다.