题目描述

如果一个数的数码从高位到低位不减少，就称它是一个上升数。用十进制形式给出一个正整数 n（$n\le 10^{18}$），将它转换成 $p=2,3,\cdots ,16$ 进制，找到 n 在哪些进制下是上升数，并输出在p进制下的表示。对于 $p\gt 10$ 进制，用大写字母 A,B,C,D,E,F 表示 10,11,12,13,14,15。

输入格式

1个正整数n。

输出格式

输出若干行。每行包含一个正整数 p 和一个字符串 s，表示 n 的 p 进制表示s 是一个上升数。

样例输入

408

样例输出

7 1122
13 255

提示

$1\le n\le 10^{18}$

1024

9 1357

1234

10 1234

12345

10 12345