Palindrome in Some Base

Interview

Time limit1sMemory limit256 MB

Summary

For each N, decide whether its base B representation is a palindrome for some B from 2 to 64.

Level: Easy3 of 10
Topics: Math, Brute force, Simulation
Solved: No attempts yet

Problem

A number is a palindrome when it reads the same from left to right and from right to left. For example, 747 is a palindrome in base 10. 255 is not a palindrome in base 10, but written in base 16 it is FF, so it is a palindrome there.

Given a positive integer $N$ , decide whether some base $B$ with $2 \le B \le 64$ writes $N$ as a palindrome. Base $B$ means one position holds one of $B$ possible values. In base 10, $B$ is 10. When $B$ is larger than 10, treat the value of each position as a single digit and compare those values, and write the representation without a leading zero.

Input

Input comes from standard input. The first line has the number of test data $T$ . Each of the next $T$ lines has one integer $N$ . Every $N$ satisfies 64 to 1,000,000 inclusive.

Output

Output goes to standard output. Print one line per test datum. Print 1 if some base $B$ with $2 \le B \le 64$ writes $N$ as a palindrome, and 0 if no such base exists.

Examples3

Example 1
Input
```
3
747
255
946734
```
Expected output
```
1
1
0
```
Example 2
Input
```
2
64
1000000
```
Expected output
```
1
1
```
Example 3
Input
```
1
79
```
Expected output
```
0
```