Palindrome in base n

Base n notation writes a number with radix $n$. Decimal notation, for example, uses radix 10. A number $A_m A_{m-1} A_{m-2} \dots A_1 A_0$ written in base n has the value

$A_m A_{m-1} A_{m-2} \dots A_1 A_0 = A_m \times n^m + A_{m-1} \times n^{m-1} + A_{m-2} \times n^{m-2} + \dots + A_1 \times n^1 + A_0 \times n^0$

For example, the decimal number 12468 equals $1 \times 10^4 + 2 \times 10^3 + 4 \times 10^2 + 6 \times 10^1 + 8 \times 10^0$.

A palindrome is text that reads the same forwards and backwards. madam, level, and 12321 are palindromes. Chung-ang, university, and 54899 are not.

Given a decimal number $A$ and a radix $n$, write a program that decides whether the base n representation of $A$ is a palindrome. Each position counts as a single symbol, and the representation carries no leading zero. In other words, the representation is a palindrome when reversing the sequence of digit values leaves it unchanged.

The first line contains the number of test cases $T$ ($1 \le T \le 1\,000$).

Each of the next $T$ lines contains a decimal number $A$ ($1 \le A \le 100\,000\,000\,000$) and a radix $n$ ($2 \le n \le 16$), separated by a space.

For each test case, print 1 on its own line if the base n representation of $A$ is a palindrome, and 0 otherwise.