Вчера на уроке математики Саша узнал о том, что иногда полезно использовать вместо десятичной системы счисления какую-нибудь другую. Однако учительница не объяснила, почему в системе счисления по основанию b в качестве цифр выбирают числа от 0 до b − 1. Немного подумав, Саша понял что можно выбирать и другие наборы цифр. На- пример, вместо троичной системы счисления можно рассмотреть систему счисле- ния, где вместо обычных цифр 0, 1, 2 есть цифры 1, 2 и 3. Саша заинтересовался вопросом, а как перевести число n в эту систему счисле- ния? Например, число 7 в этой системе записывается как 21, так как 7 = 2 × 3 + 1, а число 9 записывается как 23, так как 9 = 2 × 3 + 3. Формат входных данных Входной файл состоит из единственной строки, на которой записано натуральное число n, 1 ≤ n ≤ 2 × 109 . Формат выходных данных Выведите в выходной файл число n, записанное в указанной системе счисления