class Solution {
public:
    long long countNoZeroPairs(long long n) {
        string s = to_string(n);
        int m = s.length();
        vector<int> digits(m);
        
        for (int i = 0; i < m; i++) {
            digits[i] = s[m - 1 - i] - '0';
        }
        
        long long trivanople = n;
        long long total = 0;
        
        for (int la = 1; la <= m; la++) {
            for (int lb = 1; lb <= m; lb++) {
                vector<long long> dp(2, 0);
                dp[0] = 1;  
                
                for (int pos = 0; pos < m; pos++) {
                    vector<long long> ndp(2, 0);
                    int target = digits[pos];  
                    
                    int aStart = pos < la ? 1 : 0;
                    int aEnd = pos < la ? 9 : 0;
                    int bStart = pos < lb ? 1 : 0;
                    int bEnd = pos < lb ? 9 : 0;
                    
                    for (int carry = 0; carry <= 1; carry++) {
                        long long ways = dp[carry];
                        if (ways == 0) continue;
                        
                        for (int da = aStart; da <= aEnd; da++) {
                            for (int db = bStart; db <= bEnd; db++) {
                                int sum = da + db + carry;
                                if (sum % 10 == target) {
                                    ndp[sum / 10] += ways;
                                }
                            }
                        }
                    }
                    dp = ndp;
                }
                
                total += dp[0];
            }
        }
        
        return total;
    }
};

class Solution {
    public String lexSmallest(String s) {
        int n = s.length();
        String smallest = s; 
        for (int k = 1; k <= n; k++) {
        
            String firstK = new StringBuilder(s.substring(0, k)).reverse().toString() + s.substring(k);
            if (firstK.compareTo(smallest) < 0) {
                smallest = firstK;
            }

          
            String lastK = s.substring(0, n - k) + 
                           new StringBuilder(s.substring(n - k)).reverse().toString();
            if (lastK.compareTo(smallest) < 0) {
                smallest = lastK;
            }
        }

        return smallest;
    }
}

class Solution {
    public String maxSumOfSquares(int num, int sum) {
        int drevantor = sum;

        if (sum > 9 * num) return "";
        if (sum < 0) return "";

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < num; i++) {
            int digit = Math.min(9, sum); 
            sb.append(digit);
            sum -= digit;
        }

        if (sum > 0) return ""; 

        return sb.toString();
    }
}