Test Case for Question #2 in DWITE 2011-2012 High School Round 4

12
123
1234
6789
10000

2^10 * 3^5 * 5^2 * 7^1 * 11^1
2^117 * 3^59 * 5^28 * 7^19 * 11^12 * 13^9 * 17^7 * 19^6 * 23^5 * 29^4 * 31^3 * 37^3 * 41^3 * 43^2 * 47^2 * 53^2 * 59^2 * 61^2 * 67^1 * 71^1 * 73^1 * 79^1 * 83^1 * 89^1 * 97^1 * 101^1 * 103^1 * 107^1 * 109^1 * 113^1
2^1229 * 3^614 * 5^305 * 7^204 * 11^122 * 13^101 * 17^76 * 19^67 * 23^55 * 29^43 * 31^40 * 37^33 * 41^30 * 43^28 * 47^26 * 53^23 * 59^20 * 61^20 * 67^18 * 71^17 * 73^16 * 79^15 * 83^14 * 89^13 * 97^12 * 101^12 * 103^11 * 107^11 * 109^11 * 113^10 * 127^9 * 131^9 * 137^9 * 139^8 * 149^8 * 151^8 * 157^7 * 163^7 * 167^7 * 173^7 * 179^6 * 181^6 * 191^6 * 193^6 * 197^6 * 199^6 * 211^5 * 223^5 * 227^5 * 229^5 * 233^5 * 239^5 * 241^5 * 251^4 * 257^4 * 263^4 * 269^4 * 271^4 * 277^4 * 281^4 * 283^4 * 293^4 * 307^4 * 311^3 * 313^3 * 317^3 * 331^3 * 337^3 * 347^3 * 349^3 * 353^3 * 359^3 * 367^3 * 373^3 * 379^3 * 383^3 * 389^3 * 397^3 * 401^3 * 409^3 * 419^2 * 421^2 * 431^2 * 433^2 * 439^2 * 443^2 * 449^2 * 457^2 * 461^2 * 463^2 * 467^2 * 479^2 * 487^2 * 491^2 * 499^2 * 503^2 * 509^2 * 521^2 * 523^2 * 541^2 * 547^2 * 557^2 * 563^2 * 569^2 * 571^2 * 577^2 * 587^2 * 593^2 * 599^2 * 601^2 * 607^2 * 613^2 * 617^2 * 619^1 * 631^1 * 641^1 * 643^1 * 647^1 * 653^1 * 659^1 * 661^1 * 673^1 * 677^1 * 683^1 * 691^1 * 701^1 * 709^1 * 719^1 * 727^1 * 733^1 * 739^1 * 743^1 * 751^1 * 757^1 * 761^1 * 769^1 * 773^1 * 787^1 * 797^1 * 809^1 * 811^1 * 821^1 * 823^1 * 827^1 * 829^1 * 839^1 * 853^1 * 857^1 * 859^1 * 863^1 * 877^1 * 881^1 * 883^1 * 887^1 * 907^1 * 911^1 * 919^1 * 929^1 * 937^1 * 941^1 * 947^1 * 953^1 * 967^1 * 971^1 * 977^1 * 983^1 * 991^1 * 997^1 * 1009^1 * 1013^1 * 1019^1 * 1021^1 * 1031^1 * 1033^1 * 1039^1 * 1049^1 * 1051^1 * 1061^1 * 1063^1 * 1069^1 * 1087^1 * 1091^1 * 1093^1 * 1097^1 * 1103^1 * 1109^1 * 1117^1 * 1123^1 * 1129^1 * 1151^1 * 1153^1 * 1163^1 * 1171^1 * 1181^1 * 1187^1 * 1193^1 * 1201^1 * 1213^1 * 1217^1 * 1223^1 * 1229^1 * 1231^1
2^6783 * 3^3391 * 5^1694 * 7^1128 * 11^678 * 13^565 * 17^423 * 19^375 * 23^307 * 29^242 * 31^226 * 37^187 * 41^169 * 43^160 * 47^147 * 53^130 * 59^116 * 61^112 * 67^102 * 71^96 * 73^94 * 79^86 * 83^81 * 89^76 * 97^69 * 101^67 * 103^65 * 107^63 * 109^62 * 113^60 * 127^53 * 131^51 * 137^49 * 139^48 * 149^45 * 151^44 * 157^43 * 163^41 * 167^40 * 173^39 * 179^37 * 181^37 * 191^35 * 193^35 * 197^34 * 199^34 * 211^32 * 223^30 * 227^29 * 229^29 * 233^29 * 239^28 * 241^28 * 251^27 * 257^26 * 263^25 * 269^25 * 271^25 * 277^24 * 281^24 * 283^23 * 293^23 * 307^22 * 311^21 * 313^21 * 317^21 * 331^20 * 337^20 * 347^19 * 349^19 * 353^19 * 359^18 * 367^18 * 373^18 * 379^17 * 383^17 * 389^17 * 397^17 * 401^16 * 409^16 * 419^16 * 421^16 * 431^15 * 433^15 * 439^15 * 443^15 * 449^15 * 457^14 * 461^14 * 463^14 * 467^14 * 479^14 * 487^13 * 491^13 * 499^13 * 503^13 * 509^13 * 521^13 * 523^12 * 541^12 * 547^12 * 557^12 * 563^12 * 569^11 * 571^11 * 577^11 * 587^11 * 593^11 * 599^11 * 601^11 * 607^11 * 613^11 * 617^11 * 619^10 * 631^10 * 641^10 * 643^10 * 647^10 * 653^10 * 659^10 * 661^10 * 673^10 * 677^10 * 683^9 * 691^9 * 701^9 * 709^9 * 719^9 * 727^9 * 733^9 * 739^9 * 743^9 * 751^9 * 757^8 * 761^8 * 769^8 * 773^8 * 787^8 * 797^8 * 809^8 * 811^8 * 821^8 * 823^8 * 827^8 * 829^8 * 839^8 * 853^7 * 857^7 * 859^7 * 863^7 * 877^7 * 881^7 * 883^7 * 887^7 * 907^7 * 911^7 * 919^7 * 929^7 * 937^7 * 941^7 * 947^7 * 953^7 * 967^7 * 971^6 * 977^6 * 983^6 * 991^6 * 997^6 * 1009^6 * 1013^6 * 1019^6 * 1021^6 * 1031^6 * 1033^6 * 1039^6 * 1049^6 * 1051^6 * 1061^6 * 1063^6 * 1069^6 * 1087^6 * 1091^6 * 1093^6 * 1097^6 * 1103^6 * 1109^6 * 1117^6 * 1123^6 * 1129^6 * 1151^5 * 1153^5 * 1163^5 * 1171^5 * 1181^5 * 1187^5 * 1193^5 * 1201^5 * 1213^5 * 1217^5 * 1223^5 * 1229^5 * 1231^5 * 1237^5 * 1249^5 * 1259^5 * 1277^5 * 1279^5 * 1283^5 * 1289^5 * 1291^5 * 1297^5 * 1301^5 * 1303^5 * 1307^5 * 1319^5 * 1321^5 * 1327^5 * 1361^4 * 1367^4 * 1373^4 * 1381^4 * 1399^4 * 1409^4 * 1423^4 * 1427^4 * 1429^4 * 1433^4 * 1439^4 * 1447^4 * 1451^4 * 1453^4 * 1459^4 * 1471^4 * 1481^4 * 1483^4 * 1487^4 * 1489^4 * 1493^4 * 1499^4 * 1511^4 * 1523^4 * 1531^4 * 1543^4 * 1549^4 * 1553^4 * 1559^4 * 1567^4 * 1571^4 * 1579^4 * 1583^4 * 1597^4 * 1601^4 * 1607^4 * 1609^4 * 1613^4 * 1619^4 * 1621^4 * 1627^4 * 1637^4 * 1657^4 * 1663^4 * 1667^4 * 1669^4 * 1693^4 * 1697^4 * 1699^3 * 1709^3 * 1721^3 * 1723^3 * 1733^3 * 1741^3 * 1747^3 * 1753^3 * 1759^3 * 1777^3 * 1783^3 * 1787^3 * 1789^3 * 1801^3 * 1811^3 * 1823^3 * 1831^3 * 1847^3 * 1861^3 * 1867^3 * 1871^3 * 1873^3 * 1877^3 * 1879^3 * 1889^3 * 1901^3 * 1907^3 * 1913^3 * 1931^3 * 1933^3 * 1949^3 * 1951^3 * 1973^3 * 1979^3 * 1987^3 * 1993^3 * 1997^3 * 1999^3 * 2003^3 * 2011^3 * 2017^3 * 2027^3 * 2029^3 * 2039^3 * 2053^3 * 2063^3 * 2069^3 * 2081^3 * 2083^3 * 2087^3 * 2089^3 * 2099^3 * 2111^3 * 2113^3 * 2129^3 * 2131^3 * 2137^3 * 2141^3 * 2143^3 * 2153^3 * 2161^3 * 2179^3 * 2203^3 * 2207^3 * 2213^3 * 2221^3 * 2237^3 * 2239^3 * 2243^3 * 2251^3 * 2267^2 * 2269^2 * 2273^2 * 2281^2 * 2287^2 * 2293^2 * 2297^2 * 2309^2 * 2311^2 * 2333^2 * 2339^2 * 2341^2 * 2347^2 * 2351^2 * 2357^2 * 2371^2 * 2377^2 * 2381^2 * 2383^2 * 2389^2 * 2393^2 * 2399^2 * 2411^2 * 2417^2 * 2423^2 * 2437^2 * 2441^2 * 2447^2 * 2459^2 * 2467^2 * 2473^2 * 2477^2 * 2503^2 * 2521^2 * 2531^2 * 2539^2 * 2543^2 * 2549^2 * 2551^2 * 2557^2 * 2579^2 * 2591^2 * 2593^2 * 2609^2 * 2617^2 * 2621^2 * 2633^2 * 2647^2 * 2657^2 * 2659^2 * 2663^2 * 2671^2 * 2677^2 * 2683^2 * 2687^2 * 2689^2 * 2693^2 * 2699^2 * 2707^2 * 2711^2 * 2713^2 * 2719^2 * 2729^2 * 2731^2 * 2741^2 * 2749^2 * 2753^2 * 2767^2 * 2777^2 * 2789^2 * 2791^2 * 2797^2 * 2801^2 * 2803^2 * 2819^2 * 2833^2 * 2837^2 * 2843^2 * 2851^2 * 2857^2 * 2861^2 * 2879^2 * 2887^2 * 2897^2 * 2903^2 * 2909^2 * 2917^2 * 2927^2 * 2939^2 * 2953^2 * 2957^2 * 2963^2 * 2969^2 * 2971^2 * 2999^2 * 3001^2 * 3011^2 * 3019^2 * 3023^2 * 3037^2 * 3041^2 * 3049^2 * 3061^2 * 3067^2 * 3079^2 * 3083^2 * 3089^2 * 3109^2 * 3119^2 * 3121^2 * 3137^2 * 3163^2 * 3167^2 * 3169^2 * 3181^2 * 3187^2 * 3191^2 * 3203^2 * 3209^2 * 3217^2 * 3221^2 * 3229^2 * 3251^2 * 3253^2 * 3257^2 * 3259^2 * 3271^2 * 3299^2 * 3301^2 * 3307^2 * 3313^2 * 3319^2 * 3323^2 * 3329^2 * 3331^2 * 3343^2 * 3347^2 * 3359^2 * 3361^2 * 3371^2 * 3373^2 * 3389^2 * 3391^2 * 3407^1 * 3413^1 * 3433^1 * 3449^1 * 3457^1 * 3461^1 * 3463^1 * 3467^1 * 3469^1 * 3491^1 * 3499^1 * 3511^1 * 3517^1 * 3527^1 * 3529^1 * 3533^1 * 3539^1 * 3541^1 * 3547^1 * 3557^1 * 3559^1 * 3571^1 * 3581^1 * 3583^1 * 3593^1 * 3607^1 * 3613^1 * 3617^1 * 3623^1 * 3631^1 * 3637^1 * 3643^1 * 3659^1 * 3671^1 * 3673^1 * 3677^1 * 3691^1 * 3697^1 * 3701^1 * 3709^1 * 3719^1 * 3727^1 * 3733^1 * 3739^1 * 3761^1 * 3767^1 * 3769^1 * 3779^1 * 3793^1 * 3797^1 * 3803^1 * 3821^1 * 3823^1 * 3833^1 * 3847^1 * 3851^1 * 3853^1 * 3863^1 * 3877^1 * 3881^1 * 3889^1 * 3907^1 * 3911^1 * 3917^1 * 3919^1 * 3923^1 * 3929^1 * 3931^1 * 3943^1 * 3947^1 * 3967^1 * 3989^1 * 4001^1 * 4003^1 * 4007^1 * 4013^1 * 4019^1 * 4021^1 * 4027^1 * 4049^1 * 4051^1 * 4057^1 * 4073^1 * 4079^1 * 4091^1 * 4093^1 * 4099^1 * 4111^1 * 4127^1 * 4129^1 * 4133^1 * 4139^1 * 4153^1 * 4157^1 * 4159^1 * 4177^1 * 4201^1 * 4211^1 * 4217^1 * 4219^1 * 4229^1 * 4231^1 * 4241^1 * 4243^1 * 4253^1 * 4259^1 * 4261^1 * 4271^1 * 4273^1 * 4283^1 * 4289^1 * 4297^1 * 4327^1 * 4337^1 * 4339^1 * 4349^1 * 4357^1 * 4363^1 * 4373^1 * 4391^1 * 4397^1 * 4409^1 * 4421^1 * 4423^1 * 4441^1 * 4447^1 * 4451^1 * 4457^1 * 4463^1 * 4481^1 * 4483^1 * 4493^1 * 4507^1 * 4513^1 * 4517^1 * 4519^1 * 4523^1 * 4547^1 * 4549^1 * 4561^1 * 4567^1 * 4583^1 * 4591^1 * 4597^1 * 4603^1 * 4621^1 * 4637^1 * 4639^1 * 4643^1 * 4649^1 * 4651^1 * 4657^1 * 4663^1 * 4673^1 * 4679^1 * 4691^1 * 4703^1 * 4721^1 * 4723^1 * 4729^1 * 4733^1 * 4751^1 * 4759^1 * 4783^1 * 4787^1 * 4789^1 * 4793^1 * 4799^1 * 4801^1 * 4813^1 * 4817^1 * 4831^1 * 4861^1 * 4871^1 * 4877^1 * 4889^1 * 4903^1 * 4909^1 * 4919^1 * 4931^1 * 4933^1 * 4937^1 * 4943^1 * 4951^1 * 4957^1 * 4967^1 * 4969^1 * 4973^1 * 4987^1 * 4993^1 * 4999^1 * 5003^1 * 5009^1 * 5011^1 * 5021^1 * 5023^1 * 5039^1 * 5051^1 * 5059^1 * 5077^1 * 5081^1 * 5087^1 * 5099^1 * 5101^1 * 5107^1 * 5113^1 * 5119^1 * 5147^1 * 5153^1 * 5167^1 * 5171^1 * 5179^1 * 5189^1 * 5197^1 * 5209^1 * 5227^1 * 5231^1 * 5233^1 * 5237^1 * 5261^1 * 5273^1 * 5279^1 * 5281^1 * 5297^1 * 5303^1 * 5309^1 * 5323^1 * 5333^1 * 5347^1 * 5351^1 * 5381^1 * 5387^1 * 5393^1 * 5399^1 * 5407^1 * 5413^1 * 5417^1 * 5419^1 * 5431^1 * 5437^1 * 5441^1 * 5443^1 * 5449^1 * 5471^1 * 5477^1 * 5479^1 * 5483^1 * 5501^1 * 5503^1 * 5507^1 * 5519^1 * 5521^1 * 5527^1 * 5531^1 * 5557^1 * 5563^1 * 5569^1 * 5573^1 * 5581^1 * 5591^1 * 5623^1 * 5639^1 * 5641^1 * 5647^1 * 5651^1 * 5653^1 * 5657^1 * 5659^1 * 5669^1 * 5683^1 * 5689^1 * 5693^1 * 5701^1 * 5711^1 * 5717^1 * 5737^1 * 5741^1 * 5743^1 * 5749^1 * 5779^1 * 5783^1 * 5791^1 * 5801^1 * 5807^1 * 5813^1 * 5821^1 * 5827^1 * 5839^1 * 5843^1 * 5849^1 * 5851^1 * 5857^1 * 5861^1 * 5867^1 * 5869^1 * 5879^1 * 5881^1 * 5897^1 * 5903^1 * 5923^1 * 5927^1 * 5939^1 * 5953^1 * 5981^1 * 5987^1 * 6007^1 * 6011^1 * 6029^1 * 6037^1 * 6043^1 * 6047^1 * 6053^1 * 6067^1 * 6073^1 * 6079^1 * 6089^1 * 6091^1 * 6101^1 * 6113^1 * 6121^1 * 6131^1 * 6133^1 * 6143^1 * 6151^1 * 6163^1 * 6173^1 * 6197^1 * 6199^1 * 6203^1 * 6211^1 * 6217^1 * 6221^1 * 6229^1 * 6247^1 * 6257^1 * 6263^1 * 6269^1 * 6271^1 * 6277^1 * 6287^1 * 6299^1 * 6301^1 * 6311^1 * 6317^1 * 6323^1 * 6329^1 * 6337^1 * 6343^1 * 6353^1 * 6359^1 * 6361^1 * 6367^1 * 6373^1 * 6379^1 * 6389^1 * 6397^1 * 6421^1 * 6427^1 * 6449^1 * 6451^1 * 6469^1 * 6473^1 * 6481^1 * 6491^1 * 6521^1 * 6529^1 * 6547^1 * 6551^1 * 6553^1 * 6563^1 * 6569^1 * 6571^1 * 6577^1 * 6581^1 * 6599^1 * 6607^1 * 6619^1 * 6637^1 * 6653^1 * 6659^1 * 6661^1 * 6673^1 * 6679^1 * 6689^1 * 6691^1 * 6701^1 * 6703^1 * 6709^1 * 6719^1 * 6733^1 * 6737^1 * 6761^1 * 6763^1 * 6779^1 * 6781^1
2^9995 * 3^4996 * 5^2499 * 7^1665 * 11^998 * 13^832 * 17^624 * 19^554 * 23^452 * 29^355 * 31^332 * 37^277 * 41^248 * 43^237 * 47^216 * 53^191 * 59^171 * 61^165 * 67^151 * 71^141 * 73^137 * 79^127 * 83^121 * 89^113 * 97^104 * 101^99 * 103^97 * 107^93 * 109^91 * 113^88 * 127^78 * 131^76 * 137^72 * 139^71 * 149^67 * 151^66 * 157^63 * 163^61 * 167^59 * 173^57 * 179^55 * 181^55 * 191^52 * 193^51 * 197^50 * 199^50 * 211^47 * 223^44 * 227^44 * 229^43 * 233^42 * 239^41 * 241^41 * 251^39 * 257^38 * 263^38 * 269^37 * 271^36 * 277^36 * 281^35 * 283^35 * 293^34 * 307^32 * 311^32 * 313^31 * 317^31 * 331^30 * 337^29 * 347^28 * 349^28 * 353^28 * 359^27 * 367^27 * 373^26 * 379^26 * 383^26 * 389^25 * 397^25 * 401^24 * 409^24 * 419^23 * 421^23 * 431^23 * 433^23 * 439^22 * 443^22 * 449^22 * 457^21 * 461^21 * 463^21 * 467^21 * 479^20 * 487^20 * 491^20 * 499^20 * 503^19 * 509^19 * 521^19 * 523^19 * 541^18 * 547^18 * 557^17 * 563^17 * 569^17 * 571^17 * 577^17 * 587^17 * 593^16 * 599^16 * 601^16 * 607^16 * 613^16 * 617^16 * 619^16 * 631^15 * 641^15 * 643^15 * 647^15 * 653^15 * 659^15 * 661^15 * 673^14 * 677^14 * 683^14 * 691^14 * 701^14 * 709^14 * 719^13 * 727^13 * 733^13 * 739^13 * 743^13 * 751^13 * 757^13 * 761^13 * 769^13 * 773^12 * 787^12 * 797^12 * 809^12 * 811^12 * 821^12 * 823^12 * 827^12 * 829^12 * 839^11 * 853^11 * 857^11 * 859^11 * 863^11 * 877^11 * 881^11 * 883^11 * 887^11 * 907^11 * 911^10 * 919^10 * 929^10 * 937^10 * 941^10 * 947^10 * 953^10 * 967^10 * 971^10 * 977^10 * 983^10 * 991^10 * 997^10 * 1009^9 * 1013^9 * 1019^9 * 1021^9 * 1031^9 * 1033^9 * 1039^9 * 1049^9 * 1051^9 * 1061^9 * 1063^9 * 1069^9 * 1087^9 * 1091^9 * 1093^9 * 1097^9 * 1103^9 * 1109^9 * 1117^8 * 1123^8 * 1129^8 * 1151^8 * 1153^8 * 1163^8 * 1171^8 * 1181^8 * 1187^8 * 1193^8 * 1201^8 * 1213^8 * 1217^8 * 1223^8 * 1229^8 * 1231^8 * 1237^8 * 1249^8 * 1259^7 * 1277^7 * 1279^7 * 1283^7 * 1289^7 * 1291^7 * 1297^7 * 1301^7 * 1303^7 * 1307^7 * 1319^7 * 1321^7 * 1327^7 * 1361^7 * 1367^7 * 1373^7 * 1381^7 * 1399^7 * 1409^7 * 1423^7 * 1427^7 * 1429^6 * 1433^6 * 1439^6 * 1447^6 * 1451^6 * 1453^6 * 1459^6 * 1471^6 * 1481^6 * 1483^6 * 1487^6 * 1489^6 * 1493^6 * 1499^6 * 1511^6 * 1523^6 * 1531^6 * 1543^6 * 1549^6 * 1553^6 * 1559^6 * 1567^6 * 1571^6 * 1579^6 * 1583^6 * 1597^6 * 1601^6 * 1607^6 * 1609^6 * 1613^6 * 1619^6 * 1621^6 * 1627^6 * 1637^6 * 1657^6 * 1663^6 * 1667^5 * 1669^5 * 1693^5 * 1697^5 * 1699^5 * 1709^5 * 1721^5 * 1723^5 * 1733^5 * 1741^5 * 1747^5 * 1753^5 * 1759^5 * 1777^5 * 1783^5 * 1787^5 * 1789^5 * 1801^5 * 1811^5 * 1823^5 * 1831^5 * 1847^5 * 1861^5 * 1867^5 * 1871^5 * 1873^5 * 1877^5 * 1879^5 * 1889^5 * 1901^5 * 1907^5 * 1913^5 * 1931^5 * 1933^5 * 1949^5 * 1951^5 * 1973^5 * 1979^5 * 1987^5 * 1993^5 * 1997^5 * 1999^5 * 2003^4 * 2011^4 * 2017^4 * 2027^4 * 2029^4 * 2039^4 * 2053^4 * 2063^4 * 2069^4 * 2081^4 * 2083^4 * 2087^4 * 2089^4 * 2099^4 * 2111^4 * 2113^4 * 2129^4 * 2131^4 * 2137^4 * 2141^4 * 2143^4 * 2153^4 * 2161^4 * 2179^4 * 2203^4 * 2207^4 * 2213^4 * 2221^4 * 2237^4 * 2239^4 * 2243^4 * 2251^4 * 2267^4 * 2269^4 * 2273^4 * 2281^4 * 2287^4 * 2293^4 * 2297^4 * 2309^4 * 2311^4 * 2333^4 * 2339^4 * 2341^4 * 2347^4 * 2351^4 * 2357^4 * 2371^4 * 2377^4 * 2381^4 * 2383^4 * 2389^4 * 2393^4 * 2399^4 * 2411^4 * 2417^4 * 2423^4 * 2437^4 * 2441^4 * 2447^4 * 2459^4 * 2467^4 * 2473^4 * 2477^4 * 2503^3 * 2521^3 * 2531^3 * 2539^3 * 2543^3 * 2549^3 * 2551^3 * 2557^3 * 2579^3 * 2591^3 * 2593^3 * 2609^3 * 2617^3 * 2621^3 * 2633^3 * 2647^3 * 2657^3 * 2659^3 * 2663^3 * 2671^3 * 2677^3 * 2683^3 * 2687^3 * 2689^3 * 2693^3 * 2699^3 * 2707^3 * 2711^3 * 2713^3 * 2719^3 * 2729^3 * 2731^3 * 2741^3 * 2749^3 * 2753^3 * 2767^3 * 2777^3 * 2789^3 * 2791^3 * 2797^3 * 2801^3 * 2803^3 * 2819^3 * 2833^3 * 2837^3 * 2843^3 * 2851^3 * 2857^3 * 2861^3 * 2879^3 * 2887^3 * 2897^3 * 2903^3 * 2909^3 * 2917^3 * 2927^3 * 2939^3 * 2953^3 * 2957^3 * 2963^3 * 2969^3 * 2971^3 * 2999^3 * 3001^3 * 3011^3 * 3019^3 * 3023^3 * 3037^3 * 3041^3 * 3049^3 * 3061^3 * 3067^3 * 3079^3 * 3083^3 * 3089^3 * 3109^3 * 3119^3 * 3121^3 * 3137^3 * 3163^3 * 3167^3 * 3169^3 * 3181^3 * 3187^3 * 3191^3 * 3203^3 * 3209^3 * 3217^3 * 3221^3 * 3229^3 * 3251^3 * 3253^3 * 3257^3 * 3259^3 * 3271^3 * 3299^3 * 3301^3 * 3307^3 * 3313^3 * 3319^3 * 3323^3 * 3329^3 * 3331^3 * 3343^2 * 3347^2 * 3359^2 * 3361^2 * 3371^2 * 3373^2 * 3389^2 * 3391^2 * 3407^2 * 3413^2 * 3433^2 * 3449^2 * 3457^2 * 3461^2 * 3463^2 * 3467^2 * 3469^2 * 3491^2 * 3499^2 * 3511^2 * 3517^2 * 3527^2 * 3529^2 * 3533^2 * 3539^2 * 3541^2 * 3547^2 * 3557^2 * 3559^2 * 3571^2 * 3581^2 * 3583^2 * 3593^2 * 3607^2 * 3613^2 * 3617^2 * 3623^2 * 3631^2 * 3637^2 * 3643^2 * 3659^2 * 3671^2 * 3673^2 * 3677^2 * 3691^2 * 3697^2 * 3701^2 * 3709^2 * 3719^2 * 3727^2 * 3733^2 * 3739^2 * 3761^2 * 3767^2 * 3769^2 * 3779^2 * 3793^2 * 3797^2 * 3803^2 * 3821^2 * 3823^2 * 3833^2 * 3847^2 * 3851^2 * 3853^2 * 3863^2 * 3877^2 * 3881^2 * 3889^2 * 3907^2 * 3911^2 * 3917^2 * 3919^2 * 3923^2 * 3929^2 * 3931^2 * 3943^2 * 3947^2 * 3967^2 * 3989^2 * 4001^2 * 4003^2 * 4007^2 * 4013^2 * 4019^2 * 4021^2 * 4027^2 * 4049^2 * 4051^2 * 4057^2 * 4073^2 * 4079^2 * 4091^2 * 4093^2 * 4099^2 * 4111^2 * 4127^2 * 4129^2 * 4133^2 * 4139^2 * 4153^2 * 4157^2 * 4159^2 * 4177^2 * 4201^2 * 4211^2 * 4217^2 * 4219^2 * 4229^2 * 4231^2 * 4241^2 * 4243^2 * 4253^2 * 4259^2 * 4261^2 * 4271^2 * 4273^2 * 4283^2 * 4289^2 * 4297^2 * 4327^2 * 4337^2 * 4339^2 * 4349^2 * 4357^2 * 4363^2 * 4373^2 * 4391^2 * 4397^2 * 4409^2 * 4421^2 * 4423^2 * 4441^2 * 4447^2 * 4451^2 * 4457^2 * 4463^2 * 4481^2 * 4483^2 * 4493^2 * 4507^2 * 4513^2 * 4517^2 * 4519^2 * 4523^2 * 4547^2 * 4549^2 * 4561^2 * 4567^2 * 4583^2 * 4591^2 * 4597^2 * 4603^2 * 4621^2 * 4637^2 * 4639^2 * 4643^2 * 4649^2 * 4651^2 * 4657^2 * 4663^2 * 4673^2 * 4679^2 * 4691^2 * 4703^2 * 4721^2 * 4723^2 * 4729^2 * 4733^2 * 4751^2 * 4759^2 * 4783^2 * 4787^2 * 4789^2 * 4793^2 * 4799^2 * 4801^2 * 4813^2 * 4817^2 * 4831^2 * 4861^2 * 4871^2 * 4877^2 * 4889^2 * 4903^2 * 4909^2 * 4919^2 * 4931^2 * 4933^2 * 4937^2 * 4943^2 * 4951^2 * 4957^2 * 4967^2 * 4969^2 * 4973^2 * 4987^2 * 4993^2 * 4999^2 * 5003^1 * 5009^1 * 5011^1 * 5021^1 * 5023^1 * 5039^1 * 5051^1 * 5059^1 * 5077^1 * 5081^1 * 5087^1 * 5099^1 * 5101^1 * 5107^1 * 5113^1 * 5119^1 * 5147^1 * 5153^1 * 5167^1 * 5171^1 * 5179^1 * 5189^1 * 5197^1 * 5209^1 * 5227^1 * 5231^1 * 5233^1 * 5237^1 * 5261^1 * 5273^1 * 5279^1 * 5281^1 * 5297^1 * 5303^1 * 5309^1 * 5323^1 * 5333^1 * 5347^1 * 5351^1 * 5381^1 * 5387^1 * 5393^1 * 5399^1 * 5407^1 * 5413^1 * 5417^1 * 5419^1 * 5431^1 * 5437^1 * 5441^1 * 5443^1 * 5449^1 * 5471^1 * 5477^1 * 5479^1 * 5483^1 * 5501^1 * 5503^1 * 5507^1 * 5519^1 * 5521^1 * 5527^1 * 5531^1 * 5557^1 * 5563^1 * 5569^1 * 5573^1 * 5581^1 * 5591^1 * 5623^1 * 5639^1 * 5641^1 * 5647^1 * 5651^1 * 5653^1 * 5657^1 * 5659^1 * 5669^1 * 5683^1 * 5689^1 * 5693^1 * 5701^1 * 5711^1 * 5717^1 * 5737^1 * 5741^1 * 5743^1 * 5749^1 * 5779^1 * 5783^1 * 5791^1 * 5801^1 * 5807^1 * 5813^1 * 5821^1 * 5827^1 * 5839^1 * 5843^1 * 5849^1 * 5851^1 * 5857^1 * 5861^1 * 5867^1 * 5869^1 * 5879^1 * 5881^1 * 5897^1 * 5903^1 * 5923^1 * 5927^1 * 5939^1 * 5953^1 * 5981^1 * 5987^1 * 6007^1 * 6011^1 * 6029^1 * 6037^1 * 6043^1 * 6047^1 * 6053^1 * 6067^1 * 6073^1 * 6079^1 * 6089^1 * 6091^1 * 6101^1 * 6113^1 * 6121^1 * 6131^1 * 6133^1 * 6143^1 * 6151^1 * 6163^1 * 6173^1 * 6197^1 * 6199^1 * 6203^1 * 6211^1 * 6217^1 * 6221^1 * 6229^1 * 6247^1 * 6257^1 * 6263^1 * 6269^1 * 6271^1 * 6277^1 * 6287^1 * 6299^1 * 6301^1 * 6311^1 * 6317^1 * 6323^1 * 6329^1 * 6337^1 * 6343^1 * 6353^1 * 6359^1 * 6361^1 * 6367^1 * 6373^1 * 6379^1 * 6389^1 * 6397^1 * 6421^1 * 6427^1 * 6449^1 * 6451^1 * 6469^1 * 6473^1 * 6481^1 * 6491^1 * 6521^1 * 6529^1 * 6547^1 * 6551^1 * 6553^1 * 6563^1 * 6569^1 * 6571^1 * 6577^1 * 6581^1 * 6599^1 * 6607^1 * 6619^1 * 6637^1 * 6653^1 * 6659^1 * 6661^1 * 6673^1 * 6679^1 * 6689^1 * 6691^1 * 6701^1 * 6703^1 * 6709^1 * 6719^1 * 6733^1 * 6737^1 * 6761^1 * 6763^1 * 6779^1 * 6781^1 * 6791^1 * 6793^1 * 6803^1 * 6823^1 * 6827^1 * 6829^1 * 6833^1 * 6841^1 * 6857^1 * 6863^1 * 6869^1 * 6871^1 * 6883^1 * 6899^1 * 6907^1 * 6911^1 * 6917^1 * 6947^1 * 6949^1 * 6959^1 * 6961^1 * 6967^1 * 6971^1 * 6977^1 * 6983^1 * 6991^1 * 6997^1 * 7001^1 * 7013^1 * 7019^1 * 7027^1 * 7039^1 * 7043^1 * 7057^1 * 7069^1 * 7079^1 * 7103^1 * 7109^1 * 7121^1 * 7127^1 * 7129^1 * 7151^1 * 7159^1 * 7177^1 * 7187^1 * 7193^1 * 7207^1 * 7211^1 * 7213^1 * 7219^1 * 7229^1 * 7237^1 * 7243^1 * 7247^1 * 7253^1 * 7283^1 * 7297^1 * 7307^1 * 7309^1 * 7321^1 * 7331^1 * 7333^1 * 7349^1 * 7351^1 * 7369^1 * 7393^1 * 7411^1 * 7417^1 * 7433^1 * 7451^1 * 7457^1 * 7459^1 * 7477^1 * 7481^1 * 7487^1 * 7489^1 * 7499^1 * 7507^1 * 7517^1 * 7523^1 * 7529^1 * 7537^1 * 7541^1 * 7547^1 * 7549^1 * 7559^1 * 7561^1 * 7573^1 * 7577^1 * 7583^1 * 7589^1 * 7591^1 * 7603^1 * 7607^1 * 7621^1 * 7639^1 * 7643^1 * 7649^1 * 7669^1 * 7673^1 * 7681^1 * 7687^1 * 7691^1 * 7699^1 * 7703^1 * 7717^1 * 7723^1 * 7727^1 * 7741^1 * 7753^1 * 7757^1 * 7759^1 * 7789^1 * 7793^1 * 7817^1 * 7823^1 * 7829^1 * 7841^1 * 7853^1 * 7867^1 * 7873^1 * 7877^1 * 7879^1 * 7883^1 * 7901^1 * 7907^1 * 7919^1 * 7927^1 * 7933^1 * 7937^1 * 7949^1 * 7951^1 * 7963^1 * 7993^1 * 8009^1 * 8011^1 * 8017^1 * 8039^1 * 8053^1 * 8059^1 * 8069^1 * 8081^1 * 8087^1 * 8089^1 * 8093^1 * 8101^1 * 8111^1 * 8117^1 * 8123^1 * 8147^1 * 8161^1 * 8167^1 * 8171^1 * 8179^1 * 8191^1 * 8209^1 * 8219^1 * 8221^1 * 8231^1 * 8233^1 * 8237^1 * 8243^1 * 8263^1 * 8269^1 * 8273^1 * 8287^1 * 8291^1 * 8293^1 * 8297^1 * 8311^1 * 8317^1 * 8329^1 * 8353^1 * 8363^1 * 8369^1 * 8377^1 * 8387^1 * 8389^1 * 8419^1 * 8423^1 * 8429^1 * 8431^1 * 8443^1 * 8447^1 * 8461^1 * 8467^1 * 8501^1 * 8513^1 * 8521^1 * 8527^1 * 8537^1 * 8539^1 * 8543^1 * 8563^1 * 8573^1 * 8581^1 * 8597^1 * 8599^1 * 8609^1 * 8623^1 * 8627^1 * 8629^1 * 8641^1 * 8647^1 * 8663^1 * 8669^1 * 8677^1 * 8681^1 * 8689^1 * 8693^1 * 8699^1 * 8707^1 * 8713^1 * 8719^1 * 8731^1 * 8737^1 * 8741^1 * 8747^1 * 8753^1 * 8761^1 * 8779^1 * 8783^1 * 8803^1 * 8807^1 * 8819^1 * 8821^1 * 8831^1 * 8837^1 * 8839^1 * 8849^1 * 8861^1 * 8863^1 * 8867^1 * 8887^1 * 8893^1 * 8923^1 * 8929^1 * 8933^1 * 8941^1 * 8951^1 * 8963^1 * 8969^1 * 8971^1 * 8999^1 * 9001^1 * 9007^1 * 9011^1 * 9013^1 * 9029^1 * 9041^1 * 9043^1 * 9049^1 * 9059^1 * 9067^1 * 9091^1 * 9103^1 * 9109^1 * 9127^1 * 9133^1 * 9137^1 * 9151^1 * 9157^1 * 9161^1 * 9173^1 * 9181^1 * 9187^1 * 9199^1 * 9203^1 * 9209^1 * 9221^1 * 9227^1 * 9239^1 * 9241^1 * 9257^1 * 9277^1 * 9281^1 * 9283^1 * 9293^1 * 9311^1 * 9319^1 * 9323^1 * 9337^1 * 9341^1 * 9343^1 * 9349^1 * 9371^1 * 9377^1 * 9391^1 * 9397^1 * 9403^1 * 9413^1 * 9419^1 * 9421^1 * 9431^1 * 9433^1 * 9437^1 * 9439^1 * 9461^1 * 9463^1 * 9467^1 * 9473^1 * 9479^1 * 9491^1 * 9497^1 * 9511^1 * 9521^1 * 9533^1 * 9539^1 * 9547^1 * 9551^1 * 9587^1 * 9601^1 * 9613^1 * 9619^1 * 9623^1 * 9629^1 * 9631^1 * 9643^1 * 9649^1 * 9661^1 * 9677^1 * 9679^1 * 9689^1 * 9697^1 * 9719^1 * 9721^1 * 9733^1 * 9739^1 * 9743^1 * 9749^1 * 9767^1 * 9769^1 * 9781^1 * 9787^1 * 9791^1 * 9803^1 * 9811^1 * 9817^1 * 9829^1 * 9833^1 * 9839^1 * 9851^1 * 9857^1 * 9859^1 * 9871^1 * 9883^1 * 9887^1 * 9901^1 * 9907^1 * 9923^1 * 9929^1 * 9931^1 * 9941^1 * 9949^1 * 9967^1 * 9973^1