cnt+=1, 1=1**1
cnt=1
cnt+=1, 2=2**1
cnt=2
cnt+=1, 3=3**1
cnt=3
cnt+=1, 4=4**1
cnt=4
cnt+=1, 5=5**1
cnt=5
cnt+=1, 6=6**1
cnt=6
cnt+=1, 7=7**1
cnt=7
cnt+=1, 8=8**1
cnt=8
cnt+=1, 9=9**1
cnt=9
cnt+=1, 16=4**2
cnt=10
cnt+=1, 25=5**2
cnt=11
cnt+=1, 36=6**2
cnt=12
cnt+=1, 49=7**2
cnt=13
cnt+=1, 64=8**2
cnt=14
cnt+=1, 81=9**2
cnt=15
cnt+=1, 125=5**3
cnt=16
cnt+=1, 216=6**3
cnt=17
cnt+=1, 343=7**3
cnt=18
cnt+=1, 512=8**3
cnt=19
cnt+=1, 729=9**3
cnt=20
cnt+=1, 1296=6**4
cnt=21
cnt+=1, 2401=7**4
cnt=22
cnt+=1, 4096=8**4
cnt=23
cnt+=1, 6561=9**4
cnt=24
cnt+=1, 16807=7**5
cnt=25
cnt+=1, 32768=8**5
cnt=26
cnt+=1, 59049=9**5
cnt=27
cnt+=1, 117649=7**6
cnt=28
cnt+=1, 262144=8**6
cnt=29
cnt+=1, 531441=9**6
cnt=30
cnt+=1, 2097152=8**7
cnt=31
cnt+=1, 4782969=9**7
cnt=32
cnt+=1, 16777216=8**8
cnt=33
cnt+=1, 43046721=9**8
cnt=34
cnt+=1, 134217728=8**9
cnt=35
cnt+=1, 387420489=9**9
cnt=36
cnt+=1, 1073741824=8**10
cnt=37
cnt+=1, 3486784401=9**10
cnt=38
cnt+=1, 31381059609=9**11
cnt=39
cnt+=1, 282429536481=9**12
cnt=40
cnt+=1, 2541865828329=9**13
cnt=41
cnt+=1, 22876792454961=9**14
cnt=42
cnt+=1, 205891132094649=9**15
cnt=43
cnt+=1, 1853020188851841=9**16
cnt=44
cnt+=1, 16677181699666569=9**17
cnt=45
cnt+=1, 150094635296999121=9**18
cnt=46
cnt+=1, 1350851717672992089=9**19
cnt=47
cnt+=1, 12157665459056928801=9**20
cnt=48
cnt+=1, 109418989131512359209=9**21
cnt=49