commit ab70c00d8da92222bdb1423c003b59bdbfd5008b
parent b6ae7104a0902d039a5a49cabafe4ba08d9c17c1
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat, 7 Dec 2024 07:51:09 +0100
Day 7 2024
Diffstat:
5 files changed, 959 insertions(+), 0 deletions(-)
diff --git a/2024/07/Makefile b/2024/07/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+ ${CC} -o a.out day07a.cpp
+
+b:
+ ${CC} -o b.out day07b.cpp
+
+clean:
+ rm -f a b
+
+atest: a
+ ./a.out
+
+btest: b
+ ./b.out
+
+arun: a
+ ./a.out < input
+
+brun: b
+ ./b.out < input
+
+.PHONY: a b clean atest btest arun brun
diff --git a/2024/07/b.out b/2024/07/b.out
Binary files differ.
diff --git a/2024/07/day07a.cpp b/2024/07/day07a.cpp
@@ -0,0 +1,34 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+bool possible(long long x, vector<long long>& a, int i) {
+ if (i == 0)
+ return a[0] == x;
+ if (a[i] != 0 && x % a[i] == 0)
+ return possible(x/a[i], a, i-1) || possible(x-a[i], a, i-1);
+ return possible(x-a[i], a, i-1);
+}
+
+int main() {
+ string line;
+ long long tot = 0;
+ while (getline(cin, line)) {
+ long long x, i;
+ vector<long long> a;
+ stringstream s(line);
+ s >> x;
+ char colon;
+ s >> colon;
+ while (s >> i)
+ a.push_back(i);
+ if (possible(x, a, a.size()-1))
+ tot += x;
+ }
+ cout << tot << endl;
+ return 0;
+}
diff --git a/2024/07/day07b.cpp b/2024/07/day07b.cpp
@@ -0,0 +1,51 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+long long uncat(long long x, long long y) {
+ if (y == 0)
+ return x % 10 == 0 ? x / 10 : -1;
+ while (y > 0) {
+ if (x % 10 != y % 10)
+ return -1;
+ x /= 10;
+ y /= 10;
+ }
+ return x;
+}
+
+bool possible(long long x, vector<long long>& a, int i) {
+ if (i == 0)
+ return a[0] == x;
+
+ bool p = possible(x-a[i], a, i-1);
+ if (a[i] != 0 && x % a[i] == 0)
+ p = p || possible(x/a[i], a, i-1);
+ auto u = uncat(x, a[i]);
+ if (u != -1)
+ p = p || possible(u, a, i-1);
+ return p;
+}
+
+int main() {
+ string line;
+ long long tot = 0;
+ while (getline(cin, line)) {
+ long long x, i;
+ vector<long long> a;
+ stringstream s(line);
+ s >> x;
+ char colon;
+ s >> colon;
+ while (s >> i)
+ a.push_back(i);
+ if (possible(x, a, a.size()-1))
+ tot += x;
+ }
+ cout << tot << endl;
+ return 0;
+}
diff --git a/2024/07/input b/2024/07/input
@@ -0,0 +1,850 @@
+56083790: 93 7 89 932 67 58 5
+1607: 107 43 7 81 19
+751931197720: 6 8 533 3 9 6 933 2 60 2
+34649: 1 7 859 4 9
+3125401: 62 456 52 5 1
+7547: 94 283 461 9 3
+55789: 2 253 3 4 26 8 1 4 3 2 3 7
+67811: 1 587 15 6 700 2 47 6 1
+2768025357: 835 13 85 3 258 97
+349981: 9 62 3 121 775
+2163840: 6 3 6 7 2 49 5 20 8 7 2 6
+1965744438: 6 5 7 9 3 50 1 8 68 1 73 6
+3251726208: 47 37 2 9 5 8 502 8 9 9 8
+10541: 35 8 35 8 8 16 709
+3746916524: 643 8 582 475 49
+43479: 31 57 6 4 6 2 3 920 2
+10054100: 1 3 1 6 4 795 7 1 489 53
+1503936989: 75 192 2 2 7 6 989 1
+13622: 20 95 46 7
+426: 225 1 7 79 106 11 1
+491705744: 78 63 92 213 744
+18267919039745: 815 941 6 94 2 397 3
+52556232: 5 927 620 6 232
+35026084: 1 3 768 3 8 38 4 212 8 4
+212064: 59 4 18 1 6 740 12 4
+161622: 394 2 41
+1465970090: 4 4 803 902 6 334
+4032040411837: 700 8 9 42 8 51 471 9 8
+136275307195: 7 1 5 2 1 4 1 7 90 7 192 1
+340985: 3 77 738 2 2 25
+988: 7 82 64 9 2 4 58 4 2 528
+347569061: 8 2 1 7 543 2 6 3 7 7 91 1
+5369400: 30 564 89 889 300
+8072460: 3 6 7 8 23 1 3 6 2 6 5 891
+6972: 699 59 6 9 96
+81245257: 1 88 6 4 9 25 25 6 8 1 9
+12978: 53 620 43 5 9 2
+67165854: 6 5 86 2 2 7 1 7 8 530 2 7
+2571327330: 7 1 7 96 71 6 8 1 330 53
+311570632: 9 2 9 7 954 8 1 51 9 7 4
+2347380: 3 3 7 7 7 2 3 6 41 7 315 6
+28426430214: 65 3 5 97 4 64 3 9 6 361
+2387455090: 68 2 341 4 1 4 4 5 5 8 2 8
+1318681: 7 3 81 44 37 1
+44908357: 21 8 206 35 7
+1463904: 1 5 8 7 133 67 9 46 16
+472792526: 4 18 1 6 8 195 4 7 2 3 9 3
+3690175104: 6 566 7 88 7 63 4
+6192506: 8 6 1 4 1 3 6 63 6 7 2 794
+7079642: 704 2 9 367 39
+745: 2 4 8 1 2 595 56 6 31 7
+184367913208: 39 3 9 956 5 544 9 2 84
+650706364174: 803 3 41 3 571 27 4
+4372576: 6 396 4 4 46
+53324925: 532 2 54 995 25
+10178346240: 417 3 5 565 73 576 5
+187548984: 8 586 7 246 4
+434485350: 2 3 38 864 4 387 75 38
+3006: 83 7 89 9 16
+36971650474509: 210 953 158 46 9 381
+6780975: 4 9 3 4 952 3 255 1 8 7
+158481600: 8 14 8 964 200
+87761786: 29 3 761 2 5 8 9
+11341486: 126 3 3 1 486
+1767: 408 671 4 616 9 59
+49952093: 9 9 90 418 5
+36790: 8 4 3 711 79
+64253483776: 31 4 24 1 759 3 3 19 76
+795955600: 63 3 957 26 550 4 2
+15073717792: 2 7 4 3 5 7 4 8 9 80 7 93
+5318893601: 7 730 95 688 1
+697588861548: 1 1 3 3 1 8 8 481 6 15 4 5
+4483638995: 3 1 2 1 5 8 26 69 9 2 992
+475413888: 935 856 6 99 6 42
+5444838: 8 68 4 83 6
+5405636: 4 3 450 5 636
+48897: 58 69 886 3 8 4
+2033602: 6 593 7 97 5
+122678545: 629 3 361 65 78
+32636: 9 25 3 1 4 4 51 203 2 2
+104005481: 4 2 7 3 3 3 80 85 48 1
+473121071: 5 7 7 52 4 6 5 22 81 9 72
+3411084045: 75 2 46 727 680 45
+76570949: 7 9 8 7 7 5 8 8 639 68 7 1
+1496: 6 85 4 276 706
+254999: 4 8 8 8 3 9 5 67 5 1 2 61
+163899400513: 936 568 35 5 5 13
+572558: 69 6 20 140 68
+5542152: 77 762 72 66
+659770603626: 79 682 44 828 3 5 6 70
+4599935: 3 2 696 9 81 9 605 69
+5647581: 4 1 3 304 6 72 477
+586823676: 5 8 682 3 675
+268237487194: 3 2 8 7 7 55 2 487 1 9 1
+14193504059: 31 3 223 5 36 26 4 60
+220220409: 7 865 28 399 7 5
+339946418426: 582 1 8 73 1 5 95 247 6
+780000: 50 54 6 625 2
+5865: 3 583 5
+313565: 246 8 31 11 1 65
+2290783: 29 8 7 458 4 275 4 579
+1146: 8 92 91 3 2
+562750027: 89 309 63 86 941 6 24
+3278: 2 9 7 6 7 44
+459: 2 3 39 6
+1431120: 5 7 678 92 8 40
+26405616402: 56 783 2 2 82 2 51 2 2 9
+6040: 285 1 70 16 7 2 335
+1717462100: 793 922 87 27 146 1
+6188689550: 6 8 762 1 1 8 2 6 5 9 6 50
+66816: 77 4 821 2 313
+46132511: 6 911 37 528 5 10
+103140: 53 7 9 2 3 8 7 5 6 5 18
+3733695192: 289 4 80 18 9 9 9 519 1
+11310002592: 35 3 437 581 32
+1658410170064: 4 47 53 573 8 4 8 4 6 7 4
+1578423: 4 233 9 740 3
+12792914: 9 6 3 2 910 8 71 291 2
+67366818479: 6 72 36 130 8 18 479
+13292715: 92 9 349 46 3
+16587893610312: 57 6 6 40 348 441 749
+212642864: 1 92 8 7 2 3 642 1 864
+13015307040: 9 74 1 2 98 5 6 338 80
+37248: 425 17 9 678 8
+7673: 3 4 351 382 3
+19492545: 8 77 11 437 798 2 542
+5037692049: 145 2 4 13 537 59 81
+5227115460000: 25 952 75 727 76 53
+5853837: 4 191 3 383 4
+2895816393056: 76 666 517 39 930 5 9
+871074: 37 6 5 537 2
+2562: 4 8 5 34 7 7
+128155006: 133 83 1 13 593
+38655243: 8 6 79 9 1 1 33 1 88 7 7
+37815730: 73 58 1 95 65 94
+11088: 1 3 8 35 2 9 3 91 9 898 9
+15331936: 1 9 27 84 9 56 302 2 8
+616853160528: 770 34 595 45 6 2 44
+1641140: 31 3 76 63 620
+122969391: 495 18 82 138 75
+5804719203: 670 8 90 191 63
+11081356852: 3 36 86 672 903 85 96
+267393: 545 7 49
+134713: 220 800 43 284 14
+34333934: 589 23 9 2 7 4 8 1 6 1 7
+943506: 96 92 6 91 774
+30954670: 648 1 537 9 29 72
+109409456692: 123 95 8 5 94 5 669 2
+2130162694016: 7 7 251 54 55 29 38 16
+4508697507: 7 3 5 4 6 57 56 97 504
+192249: 2 3 42 510 7 17 36 1 8 9
+1489799920: 8 442 24 61 4 8 35 196
+7546848: 189 8 729 4 594 619 8
+76609349: 8 250 7 63 5 23 37
+100845316: 8 3 24 4 1 9 4 516 6 9 5
+311787: 82 38 82 79 23
+79369486: 10 4 7 7 6 8 7 29 789 6 5
+55707589: 278 5 347 7 311 4 2 2
+1046: 205 5 21
+166041240: 36 8 7 8 587 155 8
+4249331981: 1 94 6 7 9 832 2 903
+1055: 6 20 652 4 271 8
+196560: 5 169 9 6 923 7 8 4 912
+4990: 9 8 72 56 6
+341514: 54 2 7 6 9
+39823281: 1 4 6 1 3 630 1 3 2 97 7 5
+623232732: 56 662 217 5 8 78 9 3 2
+49660512: 429 142 90 814 1
+76504346: 91 84 8 55 907 442
+89795: 38 2 831 99 2
+2969500032: 4 71 6 6 1 1 8 6 804 79 2
+3663559: 78 7 431 27 32
+86027: 8 6 96 64 11
+347112: 83 978 9 93 36
+51546: 51 54 6
+386409137: 82 23 8 46 913 7
+1091904: 5 3 7 7 541 51 6 1 726 2
+5544149483: 581 797 6 4 8 149 483
+4085638: 8 3 2 75 4 5 6 6 7 6 4 81
+18112734072: 2 9 1 2 6 6 4 2 75 2 6 6
+5519052: 88 8 751 9 1 724
+985: 39 1 595
+374115327: 74 9 1 361 2 62 45
+1504216443: 47 3 131 9 1 3 9 4 38 6 3
+61345300: 4 2 854 9 5 9 2 8 412 19
+47163200: 8 27 8 5 6 5 3 4 428 70 4
+41158: 6 1 597 991 9 1
+525198449: 81 24 5 19 78 6 49
+88799836506: 6 856 1 2 1 4 1 335 103
+6801: 63 526 3 4 431 64 3 1 3
+221941: 4 43 14 604 6 877
+405758: 67 17 7 926 268 6
+9871839: 1 9 918 59 1 83 7
+226638: 3 87 31 1 1 7 4 4 58
+567421: 565 2 42 1
+15828100087: 64 8 7 2 6 1 92 249 1 8 7
+1460382: 5 5 4 6 7 8 9 1 6 4 4 489
+41128542090: 516 95 306 26 90
+9685596: 11 176 5 499 6
+834489: 6 9 7 8 3 2 2 58 659 830
+1197651060: 50 307 2 3 129 26 6 10
+50948514: 1 845 773 78 81
+1244: 9 2 5 7 490 5 91 8 1 2 8
+225050: 855 7 79 1 37 3 626 9 7
+521432: 145 62 58 6 6
+915: 35 4 1 52 5
+10019798: 917 84 9 727 71
+11416248: 14 9 9 7 6 226 7 7 8
+20086: 572 2 484 5 3 3 4 454
+40531: 90 7 5 76 57 4
+476020832: 7 4 85 10 2 832
+17460: 2 322 3 8 9
+3656576: 11 257 4 6 2 4 8 53
+384702322: 9 381 8 46 2 7 98 934 2
+15921343: 6 45 55 1 845 727 6 6 7
+948555: 5 9 39 4 166 448 7 2 1 9
+833286: 8 465 224 1 6
+83442633: 1 794 9 4 380 4 8 6 30
+4451643516: 464 8 7 399 3 518
+6035800: 43 1 14 84 3 4 919 7
+120650823: 3 31 566 92 7
+6128187052: 6 17 127 6 56 705 1 1
+56112: 370 2 8 1 74 9 677
+31903: 523 1 61
+175384445037: 9 1 989 1 57 7 126 40
+842522: 39 42 8 63 94
+3200608226: 98 36 126 92 72
+29954: 7 73 89 5 5 7 379
+1151217: 1 2 8 8 774 4 51 7 5 244
+1415015: 56 61 59 601 7
+1200971241617: 3 147 121 4 8 411 5 20
+87892: 134 7 5 602
+856: 76 2 1 39 97 4
+3078938848: 23 7 488 212 89 992
+278502: 9 9 8 11 7 3 44 7 34 5 57
+640001160: 50 400 8 29 40
+2191382: 561 458 7 61 22 3 35
+40361724: 2 8 278 36 635 1 9 1
+14599510: 3 176 44 507 41 3 5 25
+8256533040: 824 6 10 53 268 36 3
+31936421: 3 775 10 57 9 4 908 8 5
+123320992885: 5 9 3 52 4 4 9 3 7 8 409 8
+6787076: 5 7 9 711 27 5 7 5 6 7 1 9
+126143219768: 7 8 767 85 1 4 24 7 1 8
+1363526530761: 38 88 60 784 53 52 4
+665704: 944 6 984 315 296
+335678127: 8 9 111 8 21 3 562 5 5 2
+1427809: 8 54 7 8 59 5 475
+37247712: 38 3 38 635 9
+41454019283: 913 23 4 9 49 1 928 1
+361426: 279 70 1 3 5 79 26
+211934179944: 53 7 90 401 394 4
+10651627926: 21 6 3 9 3 1 52 36 9 54 1
+13014122: 89 8 8 752 812 2 4 6 26
+10533166: 105 15 1 69 57 54 66
+13334317392: 9 2 9 2 93 16 9 1 8 29 6
+35845: 3 5 6 2 2 6 2 80 4 8 4 5
+958806273: 4 3 6 3 9 801 3 4 886 7 3
+1662: 1 447 2 89 7 2 1 3 4 4 2 8
+1204062750: 5 7 4 173 8 1 2 1 1 984 6
+106347844047: 7 7 989 7 9 19 21 50
+5243574: 3 2 5 1 9 6 25 9 7 3 905 4
+160059844256: 9 5 81 1 771 77 2 208
+757925: 1 70 427 25
+2774739: 6 75 61 85 4
+3609299: 8 568 2 9 6 20 58 75
+4052517: 8 73 981 51 6
+9197: 5 2 4 800 1 246 98 53
+2286636: 24 56 3 873 103 6 30
+25872067585: 756 924 154 6 7 5 81 5
+7091153051: 59 8 743 536 15 11
+717443: 7 173 9 7 45
+881: 7 4 14 7 832
+32120: 222 93 37 490 93
+2117: 2 9 6 8 66 2 5 53 8 7 8 77
+12032: 656 611 636 4 6 590
+227589: 3 611 1 7 9 34
+2241278: 789 1 4 2 41 8 698
+2598: 1 4 6 22 2 50 743 1 7 1 3
+115879: 21 8 990 7 9
+132890316: 2 97 685 316
+118870567: 547 36 605 70 560 5
+316511216: 4 95 3 592 6 2 91 3 7 3 5
+124350: 4 33 1 942 6
+1102002: 4 55 2 849 11
+106464836: 442 1 651 8 37
+154287: 55 4 704 2 733 93
+930014: 24 6 54 7 4 9 5
+13895470: 6 556 5 989 4 5
+22814: 5 5 1 2 6 653 9 1 5 96 6 8
+48533638: 70 9 4 6 8 7 1 3 4 869 9 2
+2828279: 2 30 5 780 98
+57540784: 6 8 1 9 7 7 38 8 5 1 792 4
+1030124933: 2 5 26 7 205 2 8 5 1 941
+40932: 566 72 4 79 97
+29104: 1 3 800 438 8
+48444: 9 39 3 46 6
+2500: 46 8 5 7 610
+47135447869: 101 70 6 641 52 1 6 2
+5638598586: 687 633 9 82 3 606
+102994668: 66 2 3 921 931 84
+1161: 1 37 214 910 1
+1286879: 501 6 4 390 454 77
+44159213957: 20 3 791 9 7 28 344 4 5
+98886480: 988 51 34 699 781
+60: 40 4 4 9 3
+10327537: 999 6 38 293 535
+120310569617: 96 41 3 7 446 979 622
+34399817046: 5 508 43 67 704 6
+1785171384: 2 9 193 6 98 969 12 2 9
+9577827: 275 6 58 78 27
+1205840: 39 377 8 5 355 2 80
+209165274738: 13 7 43 97 957 355 4
+799259160: 8 6 93 5 1 9 6 5 4 1 9 890
+14737664: 655 225 34 122 7
+9289091880: 9 71 2 5 687 529 4
+41812: 5 836 9 3 1
+129: 8 2 2 88 20 1 3
+446228143: 638 9 9 1 8 13 97 9 7
+2216793238563: 46 291 3 7 5 978 92 6 3
+24533403481: 7 8 92 1 6 8 8 775 8 7 4 1
+1785761: 324 8 8 4 6 367 4 588 5
+1822613000: 58 99 94 125 988
+5110848: 4 934 9 152
+189320592: 5 4 74 4 36 1 2 4 26 8 3
+2200066: 817 8 48 334 4 973 33
+42089099: 5 5 42 855 35 95 4
+49232576: 886 934 83 631 41 63
+8676: 46 600 90 222 6 9
+111969042432: 1 5 8 6 8 4 4 74 4 962 8 6
+346282694: 6 70 4 3 2 29 914 85 4
+8791: 11 6 1 1 6 8 97 934
+38853: 76 511 3 6 8
+399056809: 7 953 5 58 82 67 7 3 9
+342807711: 3 44 5 5 6 2 434 2 9 4 15
+8524704: 48 914 2 7 94 954 96
+137340: 3 3 24 1 1 8 446 5 9 9 7
+211943838968: 1 4 33 3 941 812 6 1 3 4
+266880: 4 25 2 9 361 417
+75006409268: 4 391 73 79 160 927 1
+20926452: 3 1 674 82 44 52
+4192096657: 698 4 3 8 42 6 3 2 54 4 1
+8066916: 5 983 69 8 5 580 132
+548778868: 841 988 3 78 40 46 7 1
+1040559: 96 8 71 93 3 1 625
+946657001: 945 1 1 650 6 5 4 9 6 3
+714882712: 16 3 6 8 1 2 8 3 610 7 9 3
+45769946: 1 784 84 695 26
+114317969980: 940 5 7 547 6 74 23 80
+377186608725: 4 385 8 9 86 6 87 1 24 1
+26128128: 2 253 29 92 130
+101628: 8 3 5 8 2 674 3
+3416: 7 46 69 4 7
+306753346: 6 7 1 72 5 7 63 631 46
+50492: 1 6 8 2 2 7 12 9 1 1
+169260086: 560 62 5 975 86
+278853120: 81 36 784 5 608
+7504553: 8 54 6 8 624 553
+665167: 24 92 6 3 9 70
+387193982747: 767 7 387 9 1 655 50
+4203828: 896 469 2 5 901 3 659
+6113: 1 52 9 1 3
+15109568581: 5 472 87 64 495 86
+77199: 8 6 5 55 1 5 3 1 3 2 41 78
+27566775: 3 301 6 305 697 4
+672: 7 4 6 2 336
+12024890207700: 962 611 9 827 795 19
+107892318: 338 7 14 6 4 3 318
+221200150: 6 2 4 50 5 3 8 38 3 4 22
+4886: 16 1 25 3 13
+22961627: 376 1 8 58 8 1 6 8 2 7
+1004796: 39 90 8 8 37 527 7 5 7 9
+82139408541: 4 1 73 8 384 962 541
+799635: 26 4 1 984 25 35
+253278581: 531 6 72 9 47 36 236 9
+107449434: 35 8 164 78 3
+36617906: 697 63 7 263 89 8 827
+740: 6 2 29 669 34
+4818883: 2 516 6 852 12 57 787
+659740: 72 7 9 51 9 6 19 2
+47340305162: 6 77 82 94 743 3 719
+129681186: 7 7 402 7 1 9 1 86
+695324: 816 85 2 752 968
+520: 22 8 8 271 9
+31726191: 7 453 6 10 191
+44082432: 415 5 99 488 38 2 64 9
+48142: 339 71 2 1 4 1
+81505848266: 4 4 5 6 9 81 4 1 848 266
+5686475: 347 14 117 261 5
+2806: 380 7 58 9 79
+50022981: 67 4 96 72 13 3 6 816 9
+4931703: 2 7 9 7 6 9 38 7 20 1 6 9
+151831669: 75 202 6 238 87 661 5
+2152935: 6 93 4 2 3 3 677 5 2 2 71
+283581: 657 73 387 965 96 3 7
+1858: 72 65 6 6 2 31 682 994
+58139: 8 93 3 651 77 4
+41433: 7 491 83 94 5
+1798676: 899 338 2
+71287: 7 1 287
+593767487: 438 1 892 664 674 87
+9171504040: 4 573 10 593 268
+123963840: 6 22 8 78 301 5
+4934: 6 8 2 9 6 98
+17274262500: 330 5 517 30 75 9
+13643845742: 6 5 799 417 7 7 1 5 8 9 2
+82443: 426 13 384 78 65
+34698: 84 76 12 6 30 3 48
+1298100692: 1 511 3 4 7 3 333 8 9 2 1
+134467: 8 8 98 72 54 7
+21938: 36 7 3 86 8
+728106: 71 9 90 9 6
+1036239: 95 14 98 97 85
+12834: 245 14 3 406 96 4 39
+1869067: 8 514 11 85 2 280 41
+3093224: 67 8 3 76 28 6 5
+3907947905376: 814 2 311 627 4 96 6
+8145923: 37 64 5 8 86
+3760433: 9 5 207 84 4 8 4 5 3 2 5 8
+703560842: 1 8 2 533 5 6 1 1 20 4 4 3
+84702: 3 3 8 10 9 162 138
+1854627894: 9 85 949 55 4 89 6 63
+212488452: 6 5 2 968 5 927 292 52
+2639: 29 65 28 6 1
+8872: 6 4 8 7 7 9 7 362 25 8 1 7
+9183433: 7 1 5 527 2 6 5 5 4 2 3 3
+872676: 73 6 77 9 69 9 53 732 7
+89407: 34 95 5 69 7 45
+7326974: 6 7 6 28 1 1 7 1 8 69 4
+4335417: 6 69 2 414 8 17 9
+3118380: 311 83 1 80
+6997518451: 649 3 6 599 38 2 9 9 51
+692: 31 46 45 502 68
+223725648: 74 574 1 3 563 3 16 66
+1736100: 81 451 8 5 643
+86403: 26 65 943 7 83
+42101628673: 6 6 8 75 10 1 58 327 7
+4279409520: 92 1 3 29 7 1 8 5 6 4 722
+38262285: 4 9 2 207 55 283 1 2
+15694: 956 16 144 9 245 1
+290897817: 49 1 4 2 8 3 3 2 1 75 3 17
+36153083: 4 5 638 280 390 75 8
+17073311: 5 3 97 8 16 5 674 7 884
+2630402985990: 932 414 46 228 6 65
+8456: 2 324 461 4 8 7 93 516
+1866: 12 3 48 4 6 3 169 923
+936323046: 6 5 9 8 3 32 1 304 6 1 1
+83735645: 2 2 2 483 1 1 57 6 3 4 1 2
+19300233286826: 7 3 901 797 34 102 27
+435872007: 32 514 500 53 4
+633652800: 2 8 532 2 7 600 88 11 1
+8065: 6 36 36 34 255
+166518: 84 5 8 844 8 8 87 2
+305292: 3 54 4 4 7 43 8 6 3 412
+37620: 6 2 70 6 1
+2435900740: 2 7 95 8 443 92 1 91 70
+4843: 1 31 44 3 193 3 417 6
+2839188: 42 227 768 23 66
+2056845: 7 64 583 35 57
+6104: 253 90 461 7 473 3
+50592: 15 8 385 60 32
+962693911: 706 804 4 8 60 8 53 3
+962: 194 1 1 4 109 7 9 43 6 8
+103923456: 81 2 9 452 2 64 84 8
+21196: 43 4 58 600 2 44
+27635641600: 2 4 72 1 165 6 80 424 5
+244415360: 3 7 54 481 941 20
+61436253: 989 926 363 782 67
+26144169424: 245 5 7 7 50 24 76 62 2
+436321776: 671 8 69 589 2
+78781130100: 87 534 52 6 9 900
+14607: 5 184 8 2 9 28 8 2 59 3 9
+22411339: 223 71 8 9 3 948 61 9
+9569229: 956 89 3 25 4
+14623182843: 1 2 50 56 9 7 7 7 6 843
+2746: 701 46 3 7 308 190
+473279: 73 86 96 31 95
+83008: 690 118 713 787 88
+3568192: 4 53 246 9 4 74 64 98 8
+8507525834: 92 99 7 934 34
+1005791960: 2 5 4 368 6 3 1 1 4 949 4
+320458: 474 8 4 5 20 65 21 4 36
+1281302: 361 2 76 6 97 7 754 5 7
+88145: 5 7 6 7 3 2 983 87 4 1 8 2
+337502756: 699 482 196 43 57 55
+346898213: 34 6 6 3 76 2 93 1 5 4 7
+60369: 7 4 81 5 2 377
+5415: 284 7 70 3 5
+61466445: 373 744 570 55 95
+18402973160: 7 48 3 2 6 1 4 82 1 5 3 7
+2730744248: 5 903 9 32 514
+1551240: 190 3 36 8 40
+1024788284922: 4 1 55 67 81 4 53 461 2
+7342736119: 831 470 69 38 47 4
+3927: 5 7 3 24 25
+2400060: 93 5 9 53 255
+982227586: 98 22 19 8 585
+496314: 7 56 19 719 6
+4040257535: 6 9 668 1 3 4 7 4 224 6 1
+13483151031: 13 769 31 564 977
+46403: 8 54 401 37 66
+45397: 2 6 91 73 6 91 97 1 94
+4447366: 577 5 8 77
+2625719950: 872 78 259 82 469
+296: 4 7 189 2 94
+166198958330: 166 198 1 7 86 72 329
+36855: 46 2 57 9 39 1
+705672: 6 8 5 8 7 7 53 840 648
+493746168: 7 7 8 8 2 1 3 1 5 270 8 8
+686609000: 77 4 837 7 7 55 2 964
+602767: 8 1 5 955 5 121 780 5 7
+1022401: 497 696 857
+10384: 9 2 944
+21426: 65 2 50 596 26 15 3 8 7
+9385241: 155 60 9 8 88 16 7 5 7 5
+3775338000: 66 67 375 152 498
+217246229919: 3 61 38 69 7 6 29 922
+51802633975: 740 7 2 40 3 230 966 9
+4452: 5 813 380 7
+246173: 198 6 5 206 405 3 7
+562695027: 9 8 96 59 844 2 26
+1309857: 31 99 6 690 891 87
+2779776: 34 74 1 72 8
+7741497922: 90 5 9 20 8 7 797 3 1 71
+1671485818434: 43 6 993 4 5 757 4 51
+11213727676: 1 453 3 328 2 7 77
+6673501088: 2 73 8 3 3 357 6 4 7 1 4 4
+2787762: 33 809 8 79 3 759
+546764: 15 13 351 70 2 1 5 58
+136: 92 1 43
+93253: 9 3 25 3
+352868: 3 29 1 4 866
+32376156: 879 635 54 33 65 3 4
+871235: 120 12 66 35
+1831247: 128 51 4 1 247
+202176000: 8 1 1 7 6 6 9 768 5 3 5 26
+1722975: 3 572 51 646 5
+175468894: 2 74 9 6 4 57 94
+16488352: 8 5 277 62 21 3 87 8 6 8
+51385600385: 8 4 5 3 80 8 5 248 38 5
+15120984186: 65 3 6 5 1 5 1 833 66 7
+142: 7 1 6 6 122
+3014946: 4 2 799 39 7 1 1 2 96 66
+545580: 38 579 78 5 157 5
+4896: 6 810 25 5 9
+25438585: 93 7 5 7 57 59 3 5 7 2 6 7
+375110: 2 9 755 5 2
+7096: 2 4 49 1 9 7 3 63 2 24 8 2
+323424: 4 847 1 380 44
+857191: 1 500 93 6 1 3 477 2 20
+2811487360: 3 16 1 69 5 89 352 470
+9747: 6 27 32 22 5 9
+295167150085: 2 6 8 4 9 2 3 9 867 2 64 5
+22419298503: 921 387 62 1 629 575
+32775: 69 67 58 7 8
+594305316: 9 66 30 2 3 31 6
+212428348: 6 2 7 5 22 7 42 3 2 8 5 4
+6705301: 5 86 433 5 9 567 2 2 2 9
+29019: 9 31 8 4 33 70 3
+4951088: 5 2 2 9 98 34 3 1 2 420 8
+14933344994826: 18 635 212 369 7 54 9
+1880596497: 944 853 323 54 9 6
+32316: 924 209 63 27 24
+89674752: 17 1 6 8 131 93 6 2 4
+65803914: 871 310 692 96 3 81
+370805: 6 17 727 7 5
+1424: 559 847 10 8
+15075: 6 128 465 1 3 69 4 3 1
+9044785693: 45 210 4 55 7 5 694
+1622304: 8 16 5 8 3 7 8 3 366 8 9 4
+31356346: 52 603 346
+30633683680: 3 63 9 8 6 2 3 5 63 367 9
+1347: 2 96 7 190 372 482
+10184: 3 2 9 90 914 7
+401359728: 96 871 2 912 7 341
+10759876: 9 24 90 22 259 1 9 164
+8217375: 3 465 1 349 2 45 3 75
+4891840: 36 849 7 3 40 4
+8803089: 8 3 234 57 6 7 2
+3766682: 6 31 66 628 54
+320646: 87 6 6 6 609 2 9 2 5 939
+23741337: 65 485 1 3 753
+8910824: 54 165 74 8 76
+227251542: 2 171 3 74 1 345 36 6
+19602320: 3 764 52 294 51 69
+230076: 4 57 36 420 3 84
+5563429: 2 145 3 34 371 652
+74531683: 8 151 92 3 715 16 5 83
+152843330: 88 445 6 32 54 2
+3321822781: 4 1 1 450 4 568 3 9 1 2 1
+249089204069: 97 3 8 8 3 5 8 40 69
+4413375656844: 459 3 8 487 671 49 6
+1296667: 7 88 508 661 6
+17345405: 6 147 36 16 546 69 8
+465564: 655 6 303 3 9 53 9 5 3 4
+32376886: 9 6 4 598 74 42 7 7 5 4 6
+563892495: 86 96 702 2 6 495
+633298: 97 556 110 83 5 2 8
+50787046: 4 62 953 204 634
+87390: 68 18 67 72 3
+2403240558: 1 768 18 7 755 5 8
+12412077102: 50 3 6 82 783 9 5 1 7 6
+331930: 1 840 5 56 7 76 614
+936742758688: 93 674 275 8 688
+51431418948: 8 3 3 6 4 1 1 38 61 90 4 5
+3299009805: 95 1 6 5 9 56 5 523 5 7 9
+5752278998995: 575 227 899 89 93
+4019250: 728 12 9 6 46
+24575905: 3 7 5 628 167 2 8 7 6 3 7
+22631446711: 867 498 156 84 4 52 3
+4827: 1 6 70 820 713 3
+46502100: 34 4 46 270 5
+3280728: 40 97 1 2 1 5 4 9 92 8
+161993: 7 7 179 1 27 733
+7222928744: 87 343 1 2 3 81 1 3 242
+131281481: 5 146 1 370 238 6 80
+102633899: 34 3 62 760 629 7
+403551: 58 772 1 62 9
+4798692: 3 42 4 9 95 948 1 453 4
+4642: 56 1 16 5 60 22
+3925858: 392 5 85 5 3
+10078111: 33 76 2 97 84 9 55
+42102630: 830 2 9 5 1 5 9 3 399 6 5
+3444562: 352 5 5 89 9 832 9 73 9
+3813120: 414 28 38 993 8
+504489: 679 6 82 730 337
+58166874176: 3 7 4 1 147 5 6 7 409 8 8
+63099786651: 7 150 8 8 62 1 1 10 8 1 6
+115684: 3 674 3 1 5 4 9 5 7 6 8 8
+1118059280: 3 6 6 9 382 1 8 1 542 5
+218297: 916 7 6 34 82 3 1
+3152907481916: 381 25 4 331 81 9 16
+36711001901: 1 9 4 88 7 9 8 5 1 259 3 7
+3150538559: 6 99 6 5 5 3 1 1 3 742 9
+17007278: 58 9 1 6 90 343 3 278
+2796157: 76 4 45 4 864 6 247
+2480886: 530 65 9 8 475 5 6
+396507829: 37 24 4 610 782 9
+2694431: 6 4 60 5 2 9 898 30 431
+35304: 43 99 8 89 23
+27636008: 80 5 135 5 1 84 7 8
+25806: 3 8 3 49 298 69
+62775: 30 23 81 4 81
+21282: 599 4 17 65 36 1 288 2
+270043318363553: 458 88 9 7 289 67 5 5 2
+555: 2 2 16 1 201
+46368: 8 6 69 6 8
+436: 283 7 79 64 3
+1190: 29 70 2 3 199 790
+8299183120: 49 9 6 249 82 4 4 292
+38489155322: 3 30 347 4 7 74 2 6 3 4 1
+239345596803: 23 934 5 5 96 803
+85926648539: 8 70 1 1 5 135 11 39
+307820736: 8 3 6 7 8 65 652 9 9 4 2 6
+6377: 7 8 305 4 63 15 572
+1386630: 1 4 6 1 2 24 7 4 6 4 4 866
+16506803786: 3 611 1 9 7 9 1 7 6 6 1 84
+434593488: 543 23 4 1 7 9 7 9 5 2 88
+2398860: 3 2 3 6 1 6 423 2 5 7 9 9
+506942: 8 9 121 814 7 176 412
+1457: 412 17 698 326 4
+167420: 380 4 1 1 110
+906118132140: 924 5 5 8 9 242 4 2 90
+200736: 697 32 9
+126228: 21 25 533 218 6
+187376052: 57 623 316 872 692
+464: 4 27 27 406
+3459390027: 934 97 37 9 42 2 80 3
+597495: 1 892 586 3 4 574 43 5
+74239: 933 84 73
+85839: 85 8 13 26
+3660622: 6 6 598 23 799
+86013549308: 222 562 971 1 71
+36147: 36 1 50 1
+564169489795: 5 28 986 67 61 1 9 7 9 5
+485744688: 3 34 9 40 5 8 59 4 12 1
+2647095: 992 8 706 37 305
+435372: 33 7 18 4 12 7 6 853 5
+66136: 8 8 1 6 1 9 2 175 5 72 7 8
+509184085: 2 1 90 60 544 8 4
+332208: 41 518 8 8 1
+4450: 34 6 99 349 2
+1393: 7 546 50 782 8
+186344378: 2 77 32 344 376
+243349150: 88 4 66 803 319
+18989094942: 23 8 6 4 84 9 2 3 1 9 41
+199257670: 8 19 988 243 582 4
+451: 58 6 103
+76860461698: 1 2 1 7 3 2 63 5 4 61 698
+1772246412: 683 72 53 9 6 4 12
+51561: 211 61 18 2 2 5
+5166: 475 8 33 6
+39670700: 1 94 5 134 310
+633879523: 12 176 36 51 6 3 523
+50200413: 538 74 2 82 13
+456540907: 1 52 3 5 40 784 71 49 1
+22962349: 3 2 16 953 8 982 368
+42648902962: 5 4 8 66 7 345 295 5 7
+208380828656: 2 818 5 5 52 3 5 2 4 814
+155258217: 8 3 391 8 9 6 624 7 2 3 9
+2496037526: 21 8 1 16 52 27 7 98 26
+9212: 16 3 773 6 996
+601724: 3 19 283 1 5 5 7 7 2 1 4 1
+45260: 3 30 47 5 5
+372738: 81 46 9 4 8
+209: 23 80 59 47
+109860660: 2 7 437 1 27 165 4
+7165120475: 9 5 154 5 4 5 1 5 53 5 85
+107002: 49 6 6 324 8 74
+59885184773: 90 864 758 31 508 2
+808339: 197 43 7 2 541 6 11 74
+3372115896917: 8 4 5 7 4 5 9 28 57 91 7
+696960: 1 985 3 67 660
+888723: 9 88 34 3 33
+25780342: 883 965 22 7 634
+12446: 7 5 3 1 46
+1154575: 25 3 405 615 9 9 7 73
+130222: 3 73 18 331 799
+69984: 5 1 8 416 715 141 4 1
+125837559077: 4 631 91 6 2 5 9 9 4 987
+204368465: 748 609 293 3 514 9
+11360: 6 6 316 32 96
+21510322: 9 6 3 6 55 1 605 962 2
+2410331315: 574 247 6 195 17
+21453306: 48 17 66 5 93 52 5 81
+879180066715: 1 5 4 7 6 5 8 2 319 209 7
+601412430: 15 4 14 124 30
+495281224: 1 4 5 4 6 6 8 4 8 81 224
+2787: 8 56 8 4 735 4
+60651324: 2 9 787 74 69 29 2 8 6
+640: 38 3 479 41 6
+3905: 33 16 589
+77339: 5 7 55 15 73 5 2 45 644
+3541: 12 429 1 8 5
+1326529390: 7 3 8 95 7 24 8 43 2 8 3 4
+832692726: 29 739 40 1 7 28
+1236216182: 12 3 55 6 7 4 61 85
+20258: 5 112 36 98 1
+1743830998: 58 5 638 498 1 6 8 1
+165440626713: 5 4 44 188 6 2 67 15
+12797250091: 4 1 4 480 717 1 8 581 3
+4612461: 84 9 61 9 70 7 1
+7807: 776 4 7
+212503200009: 17 9 89 5 75 800 5 52 9
+370784953: 6 8 4 7 51 7 15 765 15 3
+44289: 57 1 763 31 4
+54450: 2 2 14 65 450
+649705: 888 3 1 5 58 366 1 133
+64594944: 7 9 688 652 9
+21238: 53 6 9 38 528
+16512: 2 2 2 42 192
+334461: 107 390 8 86 4 527 4
+91261614: 7 9 67 39 9 4 2 5 5 46 66
+3479: 749 391 2 3 53
+8253: 815 6 92 2 1
+37276513: 6 500 12 4 442 7 1
+2351539246: 691 381 457 48 46
+9169: 5 94 8 2 9 8 4 3 541 3 4 2
+34618020: 20 6 1 1 48 70 6
+15292375: 1 83 772 766 6 8 2 23
+260442003: 8 6 3 6 390 742 6 1
+1901238316552: 2 5 7 97 4 38 316 5 52
+5443993: 537 2 21 6 502 33 158
+120969415198: 13 93 694 151 97
+217273: 8 6 5 24 3 9 1 53 8 6 7 7
+257260: 4 3 225 8 95
+3690169721929: 85 42 689 153 627
+160: 57 8 91 4 1
+331255576: 3 1 1 7 7 39 3 9 3 5 5 576
+72784124: 4 813 170 11 524
+33892892: 5 6 9 1 575 5 7 5 5 47 2 9
+853934536: 847 6 93 45 38 1
+9875: 2 149 4 577 698 4
+30902400: 222 400 1 58 6
+13064065: 67 1 45 619 7 14 52 4
+184577: 87 85 3 3 4 7
+422231: 937 5 3 9 5 299 4
+11166176: 3 66 193 34 158
+56347728: 4 8 2 66 4 26 4 964
+201232813: 83 606 9 2 616 32 810
+123424318028: 1 3 247 1 38 3 1 802 6
+4366230: 7 7 5 9 44 9 66 5
+7477050016: 772 1 631 3 2 63 4 844
+152336266333: 9 995 817 5 5 381 4 6 7
+40981217760: 58 111 842 9 35 3 8
+5766837: 139 20 7 90 386
+38401564: 96 4 4 999 4
+11135115360: 8 8 97 40 6 6 22 4 405 2
+824315949: 433 85 38 5 1 30 919
+1535881: 6 715 9 6 367 2 4 8 8 1
+18409041: 6 68 48 940 82
+16645: 739 754 355 9 9 1 3
+6022000295: 849 4 2 4 1 886 4 7 1 48
+1014087438: 979 830 48 3 26
+6758002718: 719 246 32 199 6 926
+684756: 71 590 23 7 56 1
+430296: 422 5 3 2 96
+4447: 3 441 7
+1811188: 3 713 97 810 2 8 18 1
+71286: 7 1 23 5 6
+35709696: 466 4 4 4 3 3 5 6 88 9 8
+2377492897: 6 8 2 170 654 3 6 2 8 9 7
+6132692: 10 758 95 6 629
+3922831: 855 62 74 82 8 1
+12452476: 2 91 440 77 26 5 31
+54744: 2 7 124 6
+128744272081: 32 1 860 2 4 77 3 4 2 6 1
+75755758: 7 84 79 61 4 20 4 2 3 26
+52339056: 1 867 88 7 98
+276119: 3 235 4 21 5 39
+30529: 6 3 167 4 465
+1268940: 254 80 829 60
+129626: 259 7 14 526 5 9 69 8
+5237: 519 6 41
+804267: 34 53 446 162 414
+18755: 17 8 75 4 1
+44632: 633 4 6 7
+128204825622: 1 720 87 745 4 6 1 62 4
+9536: 949 4 3 3 1
+457490: 68 7 6 55 6 55 2
+1444800: 6 26 43 50 21
+339154325: 871 32 507 326 24 5
+882711: 4 8 870 678 32
+498865: 8 99 9 73 2 4 5 24 623 2
+22755: 75 8 1 3 16 7 1 75 3 3 41
+3051450: 30 51 391 59
+37279698: 109 9 38 978 61 659
+26348935: 9 239 8 7 48 300 4 631
+15429882533: 9 8 40 486 7 56 121 4
+7372452539: 2 737 97 98 995 40
+950: 50 314 3 575 8
+70550298: 100 495 2 2 702
+817053536515: 6 46 6 315 73 7 956
+2429481600: 515 4 702 70 24
+9538543: 476 2 9 9 543
+24624323109: 76 6 3 38 378 4 746 4 9
+27418374008: 486 3 6 138 2 56 8 8
+18305285: 2 9 7 2 3 7 3 4 6 336 8 5
+99122: 8 41 4 5 3 587
+1669: 5 5 7 101 6 5 8
+90208330146: 942 6 1 57 8 957
+1063: 15 990 7 54
+82119528: 304 1 453 3 5 28 9
+354415654: 7 872 984 709 59
+4578519: 3 6 79 3 4 6 4 8 3 89 3
+22163061663: 3 87 924 98 919
+122369940: 8 69 382 265 4 45 63 9
+132274: 4 3 41 81 27 6 2 4 24 7 4
+52771515: 95 1 9 7 1 301 7 90 3 5
+15156126976: 6 3 70 9 9 3 8 4 1 9 973 3
