#include <iostream> #include <string> #include <algorithm> #include <unordered_set> std::string add(const std::string& num1, const std::string& num2, int base) { std::string result; int carry = 0; int i = num1.size() - 1, j = num2.size() - 1; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += num1[i--] - (num1[i] >= 'A' ? 'A' - 10 : '0'); if (j >= 0) sum += num2[j--] - (num2[j] >= 'A' ? 'A' - 10 : '0'); carry = sum / base; result += (sum % base >= 10 ? 'A' + sum % base - 10 : '0' + sum % base); } std::reverse(result.begin(), result.end()); return result; } bool isPalindrome(const std::string& num) { int i = 0, j = num.size() - 1; while (i < j) { if (num[i] != num[j]) return false; ++i; --j; } return true; } std::string reverseNumber(const std::string& num) { std::string reversed = num; std::reverse(reversed.begin(), reversed.end()); return reversed; } int main() { int base; std::string M; std::cin >> base >> M; std::unordered_set<std::string> seen; int steps = 0; while (steps <= 30) { if (isPalindrome(M)) { std::cout << steps << std::endl; return 0; } if (seen.count(M)) { std::cout << "Impossible" << std::endl; return 0; } seen.insert(M); M = add(M, reverseNumber(M), base); ++steps; } std::cout << "Impossible" << std::endl; return 0; }