import java.math.BigInteger;

public class prob56 {
  public static int sumdigits(BigInteger p) {
    int sum = 0;
    while (p.doubleValue() > 0.5) {
      BigInteger m = p.mod(new BigInteger("" + 10));
      sum += m.intValue();
      p = p.divide(new BigInteger("" + 10));
    }
    return sum;
  }

  public static void main(String args[])
  {
    BigInteger j;
    int i,n,s,maxs;
    maxs = 0;
    for (i = 1; i < 100; i++) {
      System.out.println("Working on " + i);
      for (n = 0; n < 100; n++) {
        j = new BigInteger("" + i);
        j = j.pow(n);
//        System.out.println("Calculating for " + i + "^" + (60+n));
        s = sumdigits(j);
        if (s > maxs) {
          maxs = s;
          System.out.println("New high value: " + i + "^" + n);
        }
      }
    }
    System.out.println("Maximum sum: " + maxs);
  }
}