회문

n진법은 밑이 $n$인 표기법이다. 예를 들어 십진법은 밑이 10이다. n진법으로 쓴 수 $A_m A_{m-1} A_{m-2} \dots A_1 A_0$이 나타내는 값은 다음과 같다.

$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$

예를 들어 십진수 12468은 $1 \times 10^4 + 2 \times 10^3 + 4 \times 10^2 + 6 \times 10^1 + 8 \times 10^0$이다.

회문(palindrome)은 앞에서 읽으나 뒤에서 읽으나 같은 글이다. madam, level, 12321은 회문이다. 반면 Chung-ang, university, 54899는 회문이 아니다.

십진수 $A$와 밑 $n$이 주어질 때, $A$를 n진법으로 표현한 결과가 회문인지 판별하는 프로그램을 작성하시오. 표현에서 각 자리는 기호 하나로 세고, 맨 앞에 0은 붙이지 않는다. 즉 자릿값의 수열을 뒤집어도 원래와 같으면 회문이다.

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

둘째 줄부터 $T$개의 줄에 걸쳐 테스트 케이스마다 십진수 $A$($1 \le A \le 100\,000\,000\,000$)와 밑 $n$($2 \le n \le 16$)이 공백을 두고 주어진다.

각 테스트 케이스마다 한 줄에 $A$의 n진법 표현이 회문이면 1을, 아니면 0을 출력한다.