print"0:
12: 2 2 3
20: 2 2 5
40: 2 2 2 5
60: 2 2 3 5
100: 2 2 5 5
120: 2 2 2 3 5
140: 2 2 5 7
143: 11 13
5141: 53 97
5144: 2 2 2 643
5146: 2 31 83
5156: 2 2 1289
5164: 2 2 1291
25564: 2 2 7 11 83
61151: 61151
61163: 31 1973
61557: 3 17 17 71
61564: 2 2 15391
62012: 2 2 37 419
62412: 2 2 3 7 743
62555: 5 12511
63412: 2 2 83 191
64542: 2 3 31 347
64544: 2 2 2 2 2 2017
66012: 2 2 3 5501
66145: 5 13229
66157: 7 13 727
67151: 7 53 181
67155: 3 5 11 11 37
67165: 5 7 19 101
67542: 2 3 11257
67546: 2 33773
67550: 2 5 5 7 193
67557: 3 7 3217
70155: 3 3 5 1559
70157: 70157
71012: 2 2 41 433
71141: 7 10163
71160: 2 2 2 3 5 593
71163: 3 3 7907
71412: 2 2 3 11 541
71557: 163 439
71571: 3 23857
72012: 2 2 3 17 353
72157: 59 1223
72412: 2 2 43 421
73012: 2 2 18253
73145: 5 14629
73162: 2 157 233
74165: 5 7 13 163"