[[問題文>練習問題#k489212c]]
 # -*- coding: utf-8 -*-
 from collections import defaultdict
 
 N = 10000
 
 # 素因数分解
 def f(n):
     res = []
     res = defaultdict(int)
     d = 2
     while d * d <= n:
         while n % d == 0:
             res.append(d)
             res[d] += 1
             n /= d
         d += 1
     if n > 1:
         res.append(n)
         res[n] += 1
     return res
 
 for i in xrange(1, N+1):
     a = f(i)
     y = i
     while 1:
         fin = 1
         for e in a:
             while a.count(e) >= 2:
                 y /= (e ** 2)
                 a.remove(e)
                 a.remove(e)
                 fin = 0
         if fin:
             break
     for k, v in a.items():
         while v >= 2:
             y /= (k * k)
             v -= 2
     x = int((i / y) ** .5)
     res = '√{0} -> '
     res = '√{0} -> '.format(i)
     if y == 1:
         print (res + '{1}').format(i, x)
         print (res + '{0}').format(x)
     elif x == 1:
         print (res + '√{1}').format(i, y)
         print (res + '√{0}').format(y)
     else:
         print (res + '{1}√{2}').format(i, x, y)
         print (res + '{0}√{1}').format(x, y)


# 初心者向け
 import math
 
 t = []
 for i in range(int(math.sqrt(10000)), 1, -1):
	 t.append(i**2)
 
 print "√" + str(1) + " -> " + str(1)
 for r in range(2, 10000 + 1):
	 u = []
	 if r in t:
		 print "√" + str(r) + " -> " + str(int(math.sqrt(r)))
	 else:
		 x = 1
		 for w in t:
			 if r % w == 0:
				 r /= w
				 x *= (int(math.sqrt(w)))
		 if x > 1:
			 print "√" + str(r*(x**2)) + " -> " + str(x) + "√" +  str(r)
		 else:
			 print "√" + str(r) + " -> " + "√" + str(r)