package main

import (
    "fmt"
    "math"
    "sort"
)

func totient(n int) int {
    tot := n
    i := 2
    for i*i <= n {
        if n%i == 0 {
            for n%i == 0 {
                n /= i
            }
            tot -= tot / i
        }
        if i == 2 {
            i = 1
        }
        i += 2
    }
    if n > 1 {
        tot -= tot / n
    }
    return tot
}

var pps = make(map[int]bool)

func getPerfectPowers(maxExp int) {
    upper := math.Pow(10, float64(maxExp))
    for i := 2; i <= int(math.Sqrt(upper)); i++ {
        fi := float64(i)
        p := fi
        for {
            p *= fi
            if p >= upper {
                break
            }
            pps[int(p)] = true
        }
    }
}

func getAchilles(minExp, maxExp int) map[int]bool {
    lower := math.Pow(10, float64(minExp))
    upper := math.Pow(10, float64(maxExp))
    achilles := make(map[int]bool)
    for b := 1; b <= int(math.Cbrt(upper)); b++ {
        b3 := b * b * b
        for a := 1; a <= int(math.Sqrt(upper)); a++ {
            p := b3 * a * a
            if p >= int(upper) {
                break
            }
            if p >= int(lower) {
                if _, ok := pps[p]; !ok {
                    achilles[p] = true
                }
            }
        }
    }
    return achilles
}

func main() {
    maxDigits := 15
    getPerfectPowers(maxDigits)
    achillesSet := getAchilles(1, 5)