Вчера на уроке саша узнал о том, что иногда полезно использовать вместо десятичной системы счисления какую-нибудь другую. однако учительница не объяснила, почему в системе счисления по основанию 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, записанное в указанной системе счисления