G.NatlanExploringYouareexploringthestunningregionofNatlan!Thisregionconsistsof$n$cities,andeachcityisratedwithanattractiveness$a_i$.AdirectededgeexistsfromCity$i$toCity$j$ifandonlyif$i<j$and$\gcd(a_i,a_j)\n