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();
    }
}

class Solution {
    public int countCoprime(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int mod = 1000000007; 
        
      
        int[][] morindale = mat;
        
        int maxVal = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxVal = Math.max(maxVal, mat[i][j]);
            }
        }
        
        long[][] dp = new long[m + 1][maxVal + 1];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int g = 0; g <= maxVal; g++) {
                if (dp[i][g] == 0) continue; 
                for (int j = 0; j < n; j++) {
                    int num = mat[i][j];
                    int newGcd = gcd(g, num);
                    dp[i + 1][newGcd] = (dp[i + 1][newGcd] + dp[i][g]) % mod;
                }
            }
        }
        
        return (int) dp[m][1];
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}