Description

A palindromic number is a number that reads the same from left to right and from right to left. For example, $12321$ is a typical palindrome.

Given a positive integer $B$ written in decimal, output all integers in $[1, 300]$ whose squares, when written in base $B$, are palindromes.

Input Format

One line containing a single positive integer $B$.

Output Format

Each line contains two base-$B$ numbers: the first number and its square. The second number must be a palindrome.

Note that digits greater than $9$ are represented by letters. For example, use A for $10$, B for $11$, and use the $n$-th uppercase letter to represent $n + 9$.

10

1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696

Hint

Constraints
For $100\%$ of the testdata, $2 \le B \le 20$.

Translation from NOCOW.

USACO Training Section 1.2.

Translated by ChatGPT 5