Bridge Repair

Advent of Code 2024 [Day 7]

07-12-2024

The Historians take you to a familiar rope bridge over a river in the middle of a jungle. The Chief isn’t on this side of the bridge, though; maybe he’s on the other side?

When you go to cross the bridge, you notice a group of engineers trying to repair it. (Apparently, it breaks pretty frequently.) You won’t be able to cross until it’s fixed.

You ask how long it’ll take; the engineers tell you that it only needs final calibrations, but some young elephants were playing nearby and stole all the operators from their calibration equations! They could finish the calibrations if only someone could determine which test values could possibly be produced by placing any combination of operators into their calibration equations (your puzzle input).

For example:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

Each line represents a single equation. The test value appears before the colon on each line; it is your job to determine whether the remaining numbers can be combined with operators to produce the test value.

Operators are always evaluated left-to-right, not according to precedence rules. Furthermore, numbers in the equations cannot be rearranged. Glancing into the jungle, you can see elephants holding two different types of operators: add (+) and multiply (*).

Only three of the above equations can be made true by inserting operators:

The engineers just need the total calibration result, which is the sum of the test values from just the equations that could possibly be true. In the above example, the sum of the test values for the three equations listed above is 3749.

Determine which equations could possibly be true. What is their total calibration result?

function evaluate(numbers: number[], operators: string[]): number {
  let result = numbers[0];
  for (let i = 0; i < operators.length; i++) {
    const nextNum = numbers[i + 1];
    if (operators[i] === '+') {
      result += nextNum;
    } else {
      result *= nextNum;
    }
  }
  return result;
}

function generateOperatorCombinations(length: number): string[][] {
  const operators = ['+', '*'];
  const result: string[][] = [];
  
  function backtrack(current: string[]) {
    if (current.length === length) {
      result.push([...current]);
      return;
    }
    for (const op of operators) {
      current.push(op);
      backtrack(current);
      current.pop();
    }
  }
  
  backtrack([]);
  return result;
}

async function main() {
  const input = await Deno.readTextFile('input.txt');
  const lines = input.trim().split('\n');
  
  let sum = 0;
  
  for (const line of lines) {
    const [testValue, numbersStr] = line.split(': ');
    const numbers = numbersStr.split(' ').map(Number);
    const targetValue = parseInt(testValue);
    
    const operatorCombinations = generateOperatorCombinations(numbers.length - 1);
    
    for (const operators of operatorCombinations) {
      if (evaluate(numbers, operators) === targetValue) {
        sum += targetValue;
        break;
      }
    }
  }
  
  console.log(`Total calibration result: ${sum}`);
}

main().catch((err) => console.error(err));

The engineers seem concerned; the total calibration result you gave them is nowhere close to being within safety tolerances. Just then, you spot your mistake: some well-hidden elephants are holding a third type of operator.

The concatenation operator (||) combines the digits from its left and right inputs into a single number. For example, 12 || 345 would become 12345. All operators are still evaluated left-to-right.

Now, apart from the three equations that could be made true using only addition and multiplication, the above example has three more equations that can be made true by inserting operators:

Adding up all six test values (the three that could be made before using only + and * plus the new three that can now be made by also using ||) produces the new total calibration result of 11387.

Using your new knowledge of elephant hiding spots, determine which equations could possibly be true. What is their total calibration result?

function evaluate(numbers: number[], operators: string[]): number {
  let result = numbers[0];
  for (let i = 0; i < operators.length; i++) {
    const nextNum = numbers[i + 1];
    switch (operators[i]) {
      case '+':
        result += nextNum;
        break;
      case '*':
        result *= nextNum;
        break;
      case '||':
        result = parseInt(`${result}${nextNum}`);
        break;
    }
  }
  return result;
}

function generateOperatorCombinations(length: number): string[][] {
  const operators = ['+', '*', '||'];
  const result: string[][] = [];
  
  function backtrack(current: string[]) {
    if (current.length === length) {
      result.push([...current]);
      return;
    }
    for (const op of operators) {
      current.push(op);
      backtrack(current);
      current.pop();
    }
  }
  
  backtrack([]);
  return result;
}

async function main() {
  const input = await Deno.readTextFile('input.txt');
  const lines = input.trim().split('\n');
  
  let sum = 0;
  
  for (const line of lines) {
    const [testValue, numbersStr] = line.split(': ');
    const numbers = numbersStr.split(' ').map(Number);
    const targetValue = parseInt(testValue);
    
    const operatorCombinations = generateOperatorCombinations(numbers.length - 1);
    
    for (const operators of operatorCombinations) {
      if (evaluate(numbers, operators) === targetValue) {
        sum += targetValue;
        break;
      }
    }
  }
  
  console.log(`Total calibration result: ${sum}`);
}

main().catch((err) => console.error(err));
Click to show the input
335808: 737 55 53 8
249329: 3 4 994 5 92 1 227 79 4
450540: 23 25 99 4 2 248 90
1011357: 398 657 35 1 927
6568206: 3 3 2 4 3 2 984 3 9 8 89 6
116675782: 1 15 695 976 4 7 60 23
241573986: 587 14 34 721 38 6
60775312: 7 626 1 5 3 1 710 9 7 9 6
276737138893: 3 4 4 47 9 809 1 3 47 4 9
9360128: 1 7 174 4 3 5 8 8 2 6 6 80
35286: 4 30 42 7 6
143022: 61 38 50 8 6 2 5 9 8 6
1812: 1 7 7 305 5 3 1 3
159720945922: 66 55 4 6 945 9 22
708627: 4 1 7 1 9 1 89 8 24 777 3
29273704: 3 489 81 9 7 47 8 75 1 4
54286922: 2 81 9 42 5 6 458 6 5 6 2
3732: 565 57 6
8295338: 30 7 627 63 128
1943922: 2 4 8 22 1 5 4 9 997 5 8 2
84731: 1 168 28 5 590
145418: 81 4 32 906 83
574017: 745 8 1 2 38 9 5 4 32 5
3733590: 362 8 71 898 966
72571864: 1 9 5 2 67 5 95 3 6 60 3
1090293987487: 249 2 306 2 4 40 547 5
33969733: 7 69 8 107 813 4 82 2 1
4800417: 1 6 72 74 1 821 30
1501: 26 6 343 940 62
98458441278: 6 84 834 7 7 2 9 3 5 8 9 9
309974: 4 9 1 6 5 5 2 3 372 2 1 96
36808: 97 370 1 910 7
530432: 3 81 287 430
88843104: 7 2 955 8 1 3 20 4 4 2 48
179432322: 718 51 8 7 7 18 1 9 9
3789361: 6 52 2 63 3 3 4 831 1
32418: 37 6 4 49 2 2 2 7 7 7 97 9
962310: 7 97 7 9 6 8 996 3 1 1 4 6
45271: 88 473 315 51 595
8504: 6 36 39 71 9
401: 4 13 10 96 3 32
56723641972: 649 874 1 103 1 972
28801032: 3 4 4 344 896 82 8
7760156856: 546 401 51 61 819
4558: 4 2 894 9 4 1 851 4 4 55
7905: 4 35 751 6
11364228: 46 26 2 2 9 527
12247841609400: 9 225 843 817 10 740
8042: 12 2 60 622 2
9883889603: 282 337 3 4 2 50 104
525217881790: 812 93 673 6 1 9 2 96
106890073: 8 9 1 47 94 7 3 7 8 51 8 1
3968: 600 847 536 1 2
27811757: 5 6 77 6 30 8 3 3 175 3 5
3491: 7 4 46 9 634
3516: 28 209 64 285 6
22254825978: 941 3 8 6 4 5 7 9 77 9 7 6
12927563: 425 72 203 2 9 26
4242440: 4 611 40 14 23
20416: 4 46 28 4 2 854 1 8 6 7 3
2773560: 1 126 3 667 58 58 15 4
362088213: 5 7 2 9 7 4 8 329 6 5 215
83711640: 837 113 1 3 40
17820: 7 3 2 5 297
2431754: 22 79 98 54 20 1 9 537
144576: 3 35 150 6 9 8 9 82 3 7
508503: 72 639 7 19 9
17527: 34 94 5 6 5
39046779: 80 488 2 62 91 288
184994439: 7 49 4 977 5 2 2 407 6
18213: 8 1 8 9 75 16
1357: 5 2 9 57 238 762 3 207
128822080: 699 3 4 15 761 5 16
661: 8 6 49 6 27
6493802: 855 7 376 6 307 973
6288328481: 5 1 44 4 5 8 674 60 4 7 1
6856682: 68 56 672 9
4027: 5 7 9 5 9 7 828 29 28 4 3
48481040777: 7 882 9 5 9 8 41 1 3 7 1 9
7259332289: 1 88 62 3 4 9 7 7 3 3 5 6
1037903789: 188 70 97 8 55
135590336: 102 903 7 16 92
3550929783: 6 5 69 6 86 5 9 2 9 7 79 6
3364209: 175 356 9 6 9
567712100: 8 9 67 61 125 1 29 823
15364831222: 30 714 5 78 3 1 149 73
5616952: 9 7 92 316 919 10 7 7
1309342320: 5 9 3 2 9 1 1 9 585 9 628
1663646227: 8 2 636 46 227
39984001: 51 23 20 289 600 9 3
2786622208902: 66 57 14 69 823 8 9
820892: 8 2 1 1 7 9 4 2 800 8 9 20
18440: 118 55 11 1 1 28
541423707: 86 7 460 68 2 2 569 3
1913097: 31 3 2 429 3 22 6 8 94
22167668600: 8 869 685 5 931
1468390473: 31 9 887 417 302 3 1 4
13410: 87 78 9 5 9
580330: 1 230 502 76 5 140
1092769: 57 396 8 42 1 298
688: 648 1 21 19
27324023314: 69 72 55 233 12
370705: 674 55 5
160293312: 9 44 7 9 8 257 7 93 94 4
1724800: 955 95 50 4 392
536452: 703 1 62 4 39 6 983 92
39331: 940 101 80 35 96
2560602548: 8 36 3 1 4 980 2 2 17 6 9
7227552: 91 7 125 4 948
1775554560: 4 1 684 8 6 169 8 2 5
36913752: 4 7 7 3 4 95 7 5 284 3 3 3
60062: 1 37 319 5 5 80 942
1799958587: 785 4 8 1 5 505 24 451
176: 3 5 2 79 1 80
198712320488: 539 8 3 1 8 600 8 3 9 2 4
4131631: 4 1 31 629 4
9507600: 43 927 550 45 139
1561110147: 739 5 8 1 4 2 528
12869: 1 917 3 13 909
300413382: 8 4 57 3 4 732 11 50 32
14045483: 5 28 4 54 82
6913138421126: 9 4 83 594 20 6 4 158 9
16994502: 90 79 92 2 502 2
183038: 8 1 6 1 4 7 8 17 6 2 93 14
1239040: 8 871 72 88 2
185571259: 6 767 18 3 8 1 5 2 9 3 7 7
23180002: 347 997 67 18 731
57746637: 55 6 532 12 887 663
91254: 570 80 2 54 1
1253723: 92 33 2 959 764
36850959: 451 4 907 336 6 8 3 9
1174211: 4 901 57 1 5 37 64
69004260: 3 9 9 6 4 2 174 51 4 3 1 9
259364: 23 3 150 6 25 57 9 5
281531220: 40 8 5 88 743 39 43 51
8631: 6 188 337 2 426 9
4897083: 381 7 1 612 4 9 77 67 3
284438: 80 8 5 2 44 9 99 2 1 5 83
21492: 7 6 722 5 20 7 27
520022: 821 633 21 89 2 217
729468: 2 453 92 764 414
7650: 40 1 8 97 18
1530209924: 3 9 363 88 8 7 8 4 992 4
124416: 2 175 8 80 9 7 2 2 349 9
183173861: 6 5 5 944 63 4 7 2 7 3 1
9636: 6 149 2 67 6
440408841: 1 9 668 4 57 866 289 7
272214: 648 42 10 1 55
41122: 62 7 5 8 84 8
1886950249797: 37 68 869 925 623
4650693555: 6 9 674 93 555
347603589: 14 14 812 4 927 9 93
12579782579: 6 93 5 876 810 18
212337312: 3 69 907 228 836
114237: 77 7 49 6 3
4211: 6 4 1 5 99 66 8
3560494: 5 91 3 69 3 48 88 35 7 2
2852256: 895 59 9 9 50 6
136441244: 55 79 314 82 47
266623: 266 5 48 5 69
1017: 5 60 78 639
383943416264: 444 6 411 769 456 8
2353506: 14 90 41 23 7 556 77 1
58826: 633 97 5 80 26
49305: 7 870 9 4 8 481
355445: 1 56 52 7 2 146 17 213
81050765: 221 81 497 6 90 1 5
196618130: 9 53 9 949 420 6 7 53 2
82522653: 4 1 312 806 2 7 3 54 15
2436676: 9 97 3 18 26 915 1 30
1700707: 6 350 43 18 1 787
598623: 4 47 2 6 4 4 1 9 7 2 458 4
315889075: 9 5 6 8 4 3 14 647 4 94 7
827996: 4 45 80 40 9 89 9 2 8 8 2
67: 1 4 9 47 6 1
240444: 8 4 43 22 5 19
22373: 8 77 4 7 9 9 62 3 34 26
18409188: 572 5 15 709 1 3
890: 122 42 5 1 55 7 8
42805855970: 6 4 7 8 8 2 8 6 3 55 1 968
177840381: 2 45 19 2 52 381
1065466092: 7 573 716 371 96
569481204: 5 694 80 456 748
6557760: 177 318 368 9 4
72785543: 3 77 350 77 8 545
15787: 537 28 424 1 326
4337983: 88 31 217 8 56 23
135743: 1 8 336 974 39 45
1864911: 60 2 42 3 37
550325433: 9 3 5 75 1 8 4 587 9 3 3 4
4087664: 8 7 6 51 7 7 1 2 142 6 7 8
2035380: 19 7 51 83 77 3
1073380: 4 2 5 9 63 2 154 82 1
13276620: 106 574 3 26 51 4 7 2 9
7105: 1 14 7 8 20 6 6 7 7
493645896073: 493 645 8 9 606 1 1 7 6
34037828751334: 381 5 9 892 7 513 27 7
2347950: 47 44 778 55 15
569296: 981 5 58 26
77163: 397 366 8 65
144310617363: 576 874 9 4 50 5 819 7
23128: 5 2 1 21 826 1
416625193: 5 65 3 8 9 8 85 81 4 71 2
313411: 1 51 846 349 6
18739179715: 36 557 12 466 11
290960: 59 27 952 8 4 7 97
132876325382: 88 584 216 92 5 3 1
18302287: 1 478 4 3 9 4 1 1 952 85
2725620: 533 9 5 17 455 6
141463: 1 2 6 46 1 6 8 2 21 1 6 1
867151509124: 135 492 4 23 3 64 4
338211: 2 72 587 4 99
15744169381: 70 6 223 3 6 93 80
41584400: 13 202 5 65 4 727
577125008: 729 696 500 81 6
2088583: 34 99 252 8 576 7
206496059697: 60 9 478 8 59 69 7 1
451453008: 31 909 522 5 48 6 44
7791467: 4 2 7 3 2 2 663 1 4 2 37 8
170162: 527 1 6 458 47 4 5 2 8 3
258996371: 18 48 4 14 5 8 6 4 4 7 8
13085344: 981 40 3 26 3 23 2 92
99589590144: 14 2 54 49 297 4 8 36
91109213: 91 10 921 1
18246445: 56 61 126 8 7 67 5 31
4005150060: 809 71 7 42 1 6 3 332 5
14457163: 48 3 571 56 4
1210255: 810 83 2 18 79
191595: 636 3 8 4 416 45 250
172873048: 755 56 487 943 565 7
53482808: 3 8 4 2 5 1 370 4 3 3 6 5
500268: 29 49 352 76
5265: 449 17 60 1 3
99110: 1 80 2 984 85
2317: 3 8 36 157 4
19716402939: 46 529 2 70 382 9 9
16339245: 1 7 96 1 9 246
918126: 3 489 5 4 622 45 9
45514: 7 51 8 1 38 1 9 6 9 21
5603955: 92 50 6 539 57
373: 46 8 1 3 2
9066632842: 896 1 6 8 8 908 3 2 84 1
5091897954: 1 119 948 6 2 8 9 4 95 5
3325917018: 330 62 67 847 21 18
38622: 962 8 3 5 113 9 3 2
49762971: 1 4 9 3 9 2 8 198 88 2 7 3
14458026011: 61 2 410 9 57 852 40 9
741: 7 2 6 60 597
118125: 4 80 369 42 3
879072: 65 796 5 4 15 883 7 1 9
12673024: 1 728 68 4 8 8
10462794933: 4 16 60 23 161 9 7 90
76824: 8 97 1 99
4130: 23 17 67 1 224 9 71 9
36500020: 71 2 8 75 164 494 821
1487012: 29 9 6 5 2 2 9 5 7 8 5 89
4921597832: 34 9 1 32 397 29 439 1
1508058874: 7 93 9 7 5 7 34 6 83 4 5
39506253: 4 514 8 2 9 8 243 2 593
1365451960: 92 2 265 4 7 8 7 62 9 4 1
2799285: 3 1 4 9 37 16 9 2 9 21 2 4
6670093: 950 59 9 8 819 87 70
38775817: 10 9 455 8 940 5 7 2 7 8
14328: 1 9 190 9 8
852135: 4 5 81 37 76 33 3
7142256: 29 8 62 4 501 4 9
26338800: 94 8 3 467 25
72600: 2 9 8 8 7 1 57 688 3 2 2 2
64749724: 997 902 8 9 556
1326048: 46 86 604 9
5671: 8 8 32 8 1 9 2 6 9 5 977
9203: 7 4 824 68 71
127988: 30 560 660 824 7
164: 4 4 2 145 3
1062409: 9 83 17 7 1 49 160 40 9
17976758976: 9 6 4 12 6 738 8 466 9
859: 1 7 70 5 84
4058: 2 62 6 31 28
159656700: 6 6 80 9 7 5 9 5 7 7 175 1
648108650: 94 626 12 9 212 436
5259206: 9 8 2 60 8 6 7 367 1 95
7698040119: 7 303 9 601 671
251898349: 77 9 94 1 344 1 560 6
1764325590: 4 71 8 664 351 5 21 92
7281855336187: 79 57 536 431 7 184
6227122235: 1 921 8 7 7 5 241 44 8 1
104601704: 7 42 73 416 9 8 1 229
252332424: 3 417 927 9 1 549 7 8 9
19873: 879 69 1 92 19 94
88433953: 595 6 4 9 56 1 619 515
247799: 253 1 1 6 4 51 8 6 4 96 4
9300: 8 4 1 1 71 1 5 1 34 3 9 9
2926326347: 97 544 2 3 34 6
17243835: 4 9 275 84 33 4 399 5
644078: 93 8 8 3 3 9 12 7 1 606
144978: 72 488 2
436611: 5 24 452 336 8 3
15957545: 18 86 907 65 4 5
6034784862: 65 182 1 3 84 345 17
3969895: 4 99 9 855 42
7040: 746 938 64 4 48
151468: 6 462 7 5 7 2 689 7 1 38
2953: 4 6 5 50
249514304: 47 551 8 68 767
1021: 1 1 3 187 814
57: 7 4 5
178105: 97 2 3 903 214
63149224: 5 9 750 56 369 4 6 6 28
7750: 2 8 8 4 82 44 9 2 8 4 795
452140: 9 33 1 7 481
113138158: 9 568 86 57 40
131941170: 68 8 379 506 657
4804: 55 9 62 9 769 60
166254470723: 1 494 549 3 5 471 613
1670599: 2 51 93 2 2 44 2 882 5
1655316816: 7 362 1 9 5 6 566 23 7
91505: 9 15 2 173 414 11
212587980: 58 66 2 841 66
932702: 60 5 4 863 704
1662189580863: 84 4 53 7 7 6 7 6 8 3 6 1
5537108: 530 269 77 2 9 21 1
466712: 5 164 58 514 4
8979: 897 1 4 2
1092529: 2 540 10 43 295 36
2826835208: 7 1 6 4 9 75 4 7 779 7 1 1
4353848242: 3 6 3 5 886 5 4 13 7 9 4 9
687048: 68 728 863 1 99
66072: 71 5 377 89 917 7
96698: 61 25 9 2 62 1 9 5 3 7 7
454883302: 5 2 81 3 9 76 2 409 45 1
95463200: 45 2 7 29 1 5 9 1 4 6 2 1
625131648: 34 942 15 593 864 72
8913: 8 855 9 49 1
6976116: 47 31 2 9 266
10728897: 81 4 7 316 5 8 2 5 1 3 9 3
269082270: 7 491 3 540 33 197 43
5170579: 51 661 9 35 79
3992014: 426 902 501 6 44
5350: 5 7 1 14 7 6 4 7 6 305 5
4746484351: 5 81 2 97 466 6 73 43
35119: 48 7 6 1 3 74 7
7038900: 4 51 54 30 79
3508: 2 907 5 52 3 610
361179: 99 4 5 40 819
4399417: 756 7 2 442 399 43
3047859: 43 529 7 9 776 33 9
121833190: 1 7 2 6 7 2 237 8 7 184 3
178252209: 3 1 138 46 5 9 1 3 4 52 5
66336839: 7 608 50 1 52 478 18
66872: 471 920 6 13 8
1015256720: 8 39 5 2 6 278 2 4 6 7 5 2
251: 3 4 3 3 144
31014766: 42 6 4 751 3 8 37 3 13 9
6555654: 4 724 10 189 47
14524926: 53 6 23 8 7 2 5 49 8 31
914760: 1 3 492 66 28
4792: 80 6 192 6 1 6 718
1723: 8 25 7 41 991 11 469 4
2997: 3 29 245 9 9
107126161282: 252 576 4 1 4 738 85
6111633: 67 84 475 8 635
3079965: 75 1 5 2 182 8 4 3 6 8 1
6254672774: 5 4 708 2 7 306 8 4 7 77
174202438500: 409 594 4 3 155 2 771
27365627611: 383 272 4 3 7 8 5 17 6 5
4832905: 6 6 38 2 171 505 6 11 5
247767: 62 2 254 776 71 928
729392: 3 56 13 33 865 2 2
135329: 371 91 28 4 173
253728382: 21 21 9 8 9 9 71 1 4 638
1261462464: 1 63 95 5 6 974 2 1 9 2 6
1691650192: 4 4 8 9 2 5 9 37 2 541 7 4
816920: 3 882 84 3 15 7 6 49 8
762754367: 3 602 36 7 4 3 1 6 41
9792171027: 831 6 918 9 6 708 7 3 6
422095: 76 30 56 9 71
15670: 2 4 144 6 67
1098607941: 2 6 3 7 3 5 21 4 751 3 9 9
56135877: 5 1 212 9 8 5 2 883 1 4 7
47: 1 8 6
8424: 79 4 1 2 6
40613332: 160 6 8 66 70 635
172730906: 6 51 7 7 128 2 5 9 18 8
30165392250: 9 3 589 2 5 4 7 6 7 5 645
3160792: 3 9 321 12 952 67
278437652: 6 464 3 1 756 9 82 2
95: 9 9 16
16160: 99 3 132 76 8 4
80634: 28 4 8 166 4 954
619542: 9 5 764 85 9 657
30308213418: 6 7 6 615 8 2 97 7 8 3 7 6
785: 313 305 156 4 7
4297503668: 8 4 3 3 2 6 358 57 6 8
21085110: 6 468 72 8 9 39 5 162
358865943072743: 452 56 5 944 8 84 745
6938002: 96 146 99 5 82
89670243: 9 3 6 860 7 3 55 4 459 3
138833049675: 8 6 850 9 83 2 378 72
1851300: 65 1 55 34 15
14518: 1 7 29 202 61
2045480: 32 2 1 3 8 752 3 5 15 2 8
323839650237: 6 935 8 995 536 667 7
1054: 19 55 9
253222253: 21 184 6 6 1 4 442 9 5
5180: 850 545 4 7 907 277 2
70841: 3 59 5 5 8
2593938251: 3 48 87 87 650 5
22103506534: 1 7 7 1 5 3 961 50 6 536
6795: 311 19 7 872 7
66586334430: 32 9 4 3 56 1 3 41 8 8 70
7237755: 5 88 8 5 5 2 4 60 7 5 4 45
403886069: 216 3 57 979 867 3 6 2
69806713: 13 4 1 247 891 232
190661651: 5 1 53 37 651
99005259: 328 105 820 99 28 59
224649: 6 13 8 360 6
191059425: 41 67 966 8 9 9
5083216: 1 9 622 3 24 2 8 2 68 80
5166000: 7 116 5 240 7 5
368016109: 8 2 12 374 108
35631897: 8 3 66 7 128 1 159 996
55577277: 958 21 7 58 694
6572928: 657 2 92 6
632016: 723 1 380 9 92 4 63
2437790: 8 4 432 2 7 4 8 6 2 88 7 7
36319489: 3 73 86 65 229 8 87 3
996152332: 3 7 9 1 9 28 914 5 2 334
5331: 872 12 5 908
319763557: 546 3 69 24 578 85
4038142687337: 258 846 9 3 26 6 733 7
47674: 2 74 393 7 87
120433: 2 678 759 12 83
333018: 95 1 2 65 114 26 7 2 3 3
70985: 65 2 2 7 93 5 22
37811: 7 14 54 5 4 9 5 2 3 5 52 9
61582362: 8 3 9 4 6 5 2 37 6 58 69
487: 81 5 82
41754942: 987 76 4 982 1 300
5295876061: 6 21 3 4 75 65 6 4 5 5 3
7398214: 9 4 485 142 11
34704975: 66 7 5 28 7 85 7 3 9 16
1114: 29 45 5 3 4
66152: 3 71 41 709 3
15727312167: 748 9 196 27 21
7801998: 500 16 70 54 1 4 78
977319222: 13 47 338 5 517 473 2
11872: 4 8 794 862 8 7
1370334: 12 53 254 7 3
1582154: 3 3 8 1 787 73 9 2 3 1 7 6
16954859: 764 73 16 5 4 19
176723591: 8 12 97 5 4 5 39 3 2 6
1300432: 6 677 8 34 7
188059782: 430 90 676 8 597 6
438453132: 4 62 2 5 6 7 646 696 39
7066: 531 2 6 1 4 1 80 8 5 596
230771: 2 511 9 442 47
24032130: 3 997 3 4 8 123 6
213283675: 53 32 8 4 5 8 7 5 8 2 3 5
2211: 43 1 23 9 2 99 917 9 2 5
1378330: 3 75 844 3 6 34 5 71 3 8
10410469186: 115 665 6 879 9 7 1 2 3
2757678: 3 22 715 32 22 1 7
6407054: 82 4 7 4 8 4 347 9 9 2 2 6
3478020: 713 116 58 44 7 6
2344259: 7 2 26 92 70 69 30
7846: 4 84 21 9 781
75283: 752 1 6 4 6
6055: 1 7 8 9 7 70 3 93 1 359
133182625: 8 9 8 1 4 20 328 5 37 1 4
9491: 42 62 9 24 9 9 834 8
362376: 752 17 89 69 28
688744: 5 766 891 853 930
15228941018806: 94 162 94 101 8 806
75274237: 6 90 2 785 762 70
1620: 3 7 5 5 71 8 2 3 1 4 93 89
187691197: 209 55 53 3 149 7 44 1
1372482488: 761 3 22 9 652 194
539876: 3 45 4 4 971
88803001: 7 98 3 932 990 30
64383625: 3 30 8 166 23 68
489: 8 14 307 51 1 18
6240563: 93 57 1 2 8 6 98 7 700
312517788: 52 76 55 336 790 901
683735489367: 869 89 2 496 655 6 84
126650: 4 74 2 5 85
172256657874: 8 6 2 256 65 78 77
55093: 909 548 32 37
1656428: 113 52 641 7 10
3066: 3 34 9 6 57
24706408: 5 54 3 9 445 5
3714913249: 829 8 9 5 3 56 41 238 9
16252190667: 8 2 45 970 5 254 6 6 1 9
4805541: 1 843 475 33 4 15 3
73: 10 1 7
218831426946: 1 2 133 9 3 1 8 6 5 334 7
54397619: 62 525 174 5 868
9241607668: 924 1 607 563 12 7 86
214: 4 86 1 67 56
8707235831: 9 62 59 449 39 9 58 31
1165: 523 6 5 2 63 34
210956368: 47 34 691 4 92 35 5 13
227725870: 227 72 558 6 9 221
3675502185: 93 8 758 56 5 645
59969697559: 995 3 9 6 592 9 7 559
45603: 2 3 8 3 7 2 8 34 10 6 7 31
17262850: 896 9 33 578 880
3897906: 5 44 5 710 4
12730524454: 553 17 23 761 4 451
245677: 339 1 5 713 405
3465742: 81 4 8 70 878 979 82
12524: 78 4 4 16 5 443 1
3695: 36 9 5 2 5
201848024: 1 5 4 7 4 824 3 6 1 7 15 7
104520: 5 1 4 5 871
56020722: 3 9 54 1 2 407 64 98 2
105179740872: 58 2 80 6 6 378 75 9
5290608161696: 775 476 1 8 8 1 6 2 533
232737864: 34 7 65 963 3 76 2 4
242592: 3 42 77 4 511 2 4 4 84 2
2400: 86 3 311 6
848250: 7 829 6 530 513 2 25 9
14116656: 5 25 394 537 62
20677761000: 2 351 269 10 1 50 219
177040: 3 6 13 49 6
14388: 8 359 3 952 2 7
3993004: 42 27 27 859 9 936 7 4
3316: 59 274 7 968 4 7 6
2291535: 5 1 78 605 97 6 45
4891072: 60 7 663 67 70
6073461828: 60 4 3 1 3 4 61 8 3 10
62154540: 35 761 8 6 441 174
35498: 9 298 6 9 9 1 57 2 5 6 5 3
403573924: 401 2 482 91 925
2554422: 50 5 32 39 102 7 78
12839262054: 7 9 74 642 323 24 5 56
1488: 88 584 300 439 77
3785: 16 1 124 27 1 4
182270: 91 2 24 8 6 16
44240820: 4 7 14 889 51 905 39
152290857209: 2 9 89 59 2 9 857 210 1
249218965: 98 5 429 412 3 7 1 8
4866048: 9 9 92 66 9
2504398: 6 67 6 500 860 75
4618017460: 3 7 5 9 8 3 7 85 44 4 9 65
16567778880: 2 4 1 79 696 15 8 279
55556: 57 91 907 9 710
347423477: 53 2 441 175 357
285: 8 4 9
186356532: 1 2 8 91 9 2 2 1 9 93 436
58803685: 7 1 7 2 6 7 490 32 1 6 8 6
1309434: 495 880 878 1 3
178509: 3 81 4 6 3 7 7
846661: 70 7 1 7 5 768 2 325
25227772: 4 910 3 46 9 135 770
1190612: 901 11 31 6 36 854 34
232694: 173 3 8 8 8 9 7 40 4 7 4 8
166664864: 166 577 8 870 6 1
1019289600: 6 8 1 3 87 4 8 1 2 896 96
3358431: 72 52 7 96 873 1
91776033: 95 60 96 28 6
786603: 7 5 50 1 927 4 3 8 9 5
17824: 91 8 5 1 9 9 3 141 46 3 9
8275465002: 8 4 862 1 5 73 326 5 4 3
1172109456: 35 7 8 6 4 850 7 6 3 56
1188: 895 14 269 5 5
85155840: 3 2 7 960 48 44
3174080729: 172 914 4 28 104 731
362835922: 24 4 1 6 514 769 5 922
576796: 2 8 91 9 5 44
4148469: 2 8 85 714 4 4 2 44 5 36
37308: 8 7 361 98 8 439 7 6
30157132500: 220 285 583 33 25
277551719: 27 755 1 5 1 20 1 509 7
1127070459: 91 4 565 8 6 99 9 75 3 3
63987740: 6 6 69 58 504 906
76945954: 54 727 98 3 6 5 9 9 5 4 2
1916249: 75 68 375 50 7
89878712: 3 8 887 78 696 17
61599828: 99 703 82 8 24 820 87
139002786: 5 3 5 6 6 8 440 72 822 7
190398146: 45 6 6 1 81 44 9 2 852 2
1151436492: 493 153 81 6 6 40 9 55
477540334: 4 3 3 8 60 91 5 8 8 4 218
199692: 515 745 22 805 7 17
256733063440: 6 4 1 73 994 898 394
3778: 6 629 2 2
5305497: 32 66 9 60 27
7472238005: 4 8 6 7 5 9 724 24 515 5
4241875: 4 601 4 44 33 56 8 47 5
7398: 7 27 550 6
610239350: 1 7 7 94 24 5 670 5 53
386: 36 1 64 93 2
1089588: 3 43 83 4 7 2 82 2 4 606
334377247: 4 29 332 436 10 6 7 85
12780096: 2 84 37 4 514
143323226904: 887 529 4 979 78
23521: 655 7 203 437 9 2 85
824354465: 850 726 1 323 3
465034: 9 28 71 5 676
6481: 53 5 4 24 25
530535: 12 1 570 50 77 5
253290: 3 466 90 5 6
125167488: 8 81 6 1 5 9 5 201 6 128
7634617: 40 9 651 45 239
2664630: 6 8 26 9 4 33 9 7 279 7
11433798: 5 861 3 27 163
1402993: 56 84 2 9 62 34
2290691532198: 884 366 708 7 5 195
824555160: 95 843 13 22 6 6
94102706908: 73 5 8 423 37 7 252 2 9
4377618265: 9 356 6 1 9 6 74 9 6 47 5
23265828315: 9 5 1 517 823 3 2 3 14
11356352700: 7 9 46 8 4 6 32 635 770
356085: 422 5 7 1 58 5 8 3 84 3 6
4931918: 5 37 9 9 9 8 921
3984130198: 432 7 155 1 2 850
12697092: 4 5 6 9 1 4 9 137 17 9 76
2044220: 147 57 4 2 23
8403733467: 822 19 60 472 19 26
1941410931: 5 8 86 2 321 4 6 2 9 2 7 1
2477: 1 6 5 8 9 5 4 2 4 529 8 28
11003235877: 4 7 9 8 5 984 9 491 16
166704731505: 5 49 4 6 5 8 34 7 4 505
3409653: 6 1 5 746 873 5 1 588
7892463: 5 695 41 142 75 813 1
331807: 63 8 1 25 7 980 40 1 5 2
111260906: 528 439 3 2 25 24
28768890: 455 655 319 675 63
9285066: 8 9 5 1 71 583 86 354
621431805570: 621 1 3 31 805 571
428953: 3 16 182 7 8 7 1 4 5 4 8 7
828786: 3 3 12 456 78 99 83 4
194276336: 93 101 276 3 32 2
4786009982: 92 94 736 333 3 51
44271360: 685 34 501 3 9 3 8 8 7
1048274530: 701 78 5 27 2 710
7172929: 96 53 4 27 8 6 14 52 6
149277925: 4 967 8 93 3 24 1
58409: 96 76 8 1 40
10374: 206 104 79 1 9 1 26
2505109320: 3 3 63 5 895 5 7 87 2 3 2
1360: 1 156 13 2 4
2595413: 4 9 62 5 57 1 7 93 9 7 2
403: 4 1 7 10 54
1488180: 92 53 5 61 993 7
12957476498: 7 948 5 667 16 843
1344925707: 39 54 824 8 36 5 155 7
7966778: 4 8 5 83 9 80 49 4 3 1 2
2375827856: 9 9 5 875 431 7 837 8 8
27957911: 617 1 6 4 2 3 6 7 6 3 78 8
237223914051: 941 2 7 2 9 5 3 10 5 7 9 7
1172738569: 2 27 3 5 85 7 2 7 5 8 9
30660: 265 9 30 2 62
285756027: 437 5 63 728 9 7 5 1 2 5
17086928567: 8 552 9 6 7 7 8 3 2 185 7
2387: 10 21 77
1670627: 839 949 87 9 99 2
89494: 887 53 740
135578: 1 2 53 71 37 3
61755521: 7 7 19 44 80
2358541152: 8 2 927 41 3 21 325 5 5
5298268754: 2 53 771 25 95 5
85910976020738: 83 599 6 480 6 20 738
238388504: 617 5 636 1 350 2
352536: 3 8 7 461 7 16 5 296
3524933: 5 7 3 11 1 534
41545238: 312 951 3 6 2 328 92 7
29538040: 216 1 1 2 332 5 41
1571: 6 3 981 7 565
2298505736: 60 8 4 5 5 5 1 44 3 42 9
5015664: 683 984 5 449 571
2837727: 6 7 2 3 6 4 1 7 508 5 33 5
80700: 87 3 8 6 50
79288: 74 62 583
2632052: 6 2 8 9 159 28 500 2 50
29028249: 44 83 2 3 716 1 72 3 3
1466917: 4 159 76 96 8 93 529
207155776894: 28 9 28 32 72 8 896
279655113: 4 1 36 91 676
54529524686: 2 7 2 1 7 2 9 9 48 6 6 685
11990: 123 45 3 3 7
87785: 602 798 63 6 7
216797: 598 55 83 4 1
12141829: 63 2 3 6 2 8 4 280 8 29 5
62153: 4 5 69 79 26 65 7 2 91
5812: 1 45 9 1 940 9 5 5 772
33338: 1 97 340 1 9 8
107101: 2 17 7 5 9 4 49 5 259 17
211172238477: 2 377 314 55 5 98 568
1116700: 10 21 318 772 859
7642: 68 731 8 41 393 810 6
3226: 8 1 92 5 5 5 3 9 1 684
3817752: 4 117 8 56 9 98 72 456
6222091: 3 1 6 600 3 6 16 7 4 3 55
32374438: 7 611 536 3 2 8 330 84
9810623: 15 82 62 5 9 15 807
3182651: 102 55 9 3 3 210 7 310
46136: 98 50 867 2 4
889: 4 80 2 4 456 9 252
190049605020: 6 3 77 4 25 82 837 990
37792782: 3 8 37 1 55 4 4 1 95 4 3
145: 28 2 99 5 5 6
520636325: 95 305 28 5 4 981 62 5
925375477: 70 9 8 5 5 32 5 1 5 47 7
493290000: 573 7 7 375 324
5457683: 8 737 32 93 85 61 9 1
4910: 72 80 9 30 83
2753378: 439 10 22 7 9 64 10 98
34148611: 19 216 77 6 295
94927: 419 55 6 5 2
698310: 4 6 5 7 702 3 7 8 5 54 6 9
58441239: 1 625 2 824 3 3 8 6 239
7516692480: 128 66 83 8 2 670
71106222600: 630 269 1 7 740 9 3 3
47097301: 9 3 560 5 1 29 9 6 89 7 8
3675: 6 9 52 10 47 31
1110: 5 6 6 6 8 1 9 54 3 1 857 3
241929: 2 690 125 863 144 4 5
45665857: 4 189 1 5 4 9 6 46 8 3 1
249745881: 63 931 1 9 251 8 82
58080: 60 475 70 16 6
7032: 5 9 2 70 6 390 1 2 792 4
64588431014: 5 2 252 13 1 90 9 7 47
1107: 2 9 1 98 75 922
316740812186: 1 9 9 7 3 950 6 768 3 6 4
8761545: 744 4 85 3 39
2661552: 6 760 82 58 104 54
12420: 3 16 50 9 5 4
441291: 9 23 5 5 9 5 2 3 7 8 13 4
8689115: 9 29 55 45 611 600 95
168750031: 5 6 6 6 4 24 77 764
843454122: 41 72 69 3 293
3331057: 1 763 436 8 7
2722: 12 5 4 3 911
246216645857: 54 71 48 1 45 857
29822010: 27 2 76 50 15 749 573
36722: 36 994 1 621 8 38 270
599783: 6 5 854 677 680 635
9116: 2 8 2 7 4 935 8 164 8 9 3
1295500: 568 30 76 379 81
190581272802240: 6 82 5 329 655 87 8 7 7
167125: 32 1 408 5 85
81900: 4 13 25 63
57580992: 5 3 138 9 2 7 302 5 8 8 9
12458534: 5 6 6 6 19 14 35 33 334
53964362670: 89 9 2 8 1 20 890 3 1
62988461250: 1 2 9 39 5 922 4 5 9 7 8 4
2132515606590: 3 1 533 5 155 3 7 658 7
2326433: 2 945 6 6 1 8 5 3 17 8 8 9
102471: 6 7 72 88 69
13112251: 6 26 849 3 99
137088990: 923 9 5 7 60 55 2 379 9
1106: 63 1 1 6 20 452
330692171: 464 96 486 9 2 59
240410: 24 619 3 371 742
589952: 58 8 286 419 4
1231246333733: 8 7 8 61 77 29 373 6
544204: 717 759 1
1126: 5 539 2 31 7
882445951: 882 445 183 766
117360: 30 8 86 5 72
744: 655 1 7 4 75
18610177: 35 6 672 407 8 547 83
2685190: 30 55 376 7 3 73 64 4 2
198279075: 42 398 62 45 75
401524: 410 977 1 48 905
239616: 5 674 361 6 2 7 6 8 6 2 4
11977700: 70 241 1 710
143761806023: 157 9 8 455 27 2 6 22 1
1483764964: 647 25 307 4 9 2 496 3
960: 5 192 1
16579224: 618 638 50 44 4 6
40551: 6 4 37 2 3 2 2 7 527 2 7
749408256: 58 4 79 9 5 87 3 8 128
16836: 6 2 7 69 6 8 8 3 51 6
61596335: 7 44 8 327 61
16694732: 766 342 23 4 655 93
46910122: 2 77 3 967 6 3 3 35 7 1
1365: 21 3 618 686 37
2226052193: 6 9 1 8 265 4 2 4 434 5 5
14626832: 1 9 2 3 67 4 183 97 3 1 2
3149: 945 3 57 5 252
2018297: 6 1 5 71 812 477
192942: 99 1 4 1 486
5896806: 3 8 1 2 983 787 9 6 60 6
33057839: 661 5 7 109 645 51 31
45120753216: 4 2 281 6 6 6 44 3 919 6
19541537: 2 4 48 724 8 1 401 62 5
45348657692: 771 231 4 6 8 6 735
95924806: 168 793 7 7 35 18 4
305481940: 96 5 57 2 1 59 113 145
12020061: 4 835 44 8 444 73 15 5
15556114: 835 115 2 81 64
14108160: 660 4 2 668 4
3005447455: 3 7 568 2 4 74 57
1856796984391: 4 58 4 77 68 6 7 7 39 2
22602: 850 4 367 6 1
123: 40 3 7 4 69
54922: 6 12 20 461 817 3 5 8 2
124872918: 821 11 6 25 7 1 721 17
70: 10 4 5
14626188: 4 9 9 8 3 435 84 9 9 6 7 3
729247255952: 3 321 9 989 5 1 5 95 2
103333: 47 56 1 3 34
9596: 95 22 2 69
25245: 9 200 724 4
499804661: 1 923 9 89 30 3 2 338 5
3603: 8 99 75 2 2 72 8 3 1 79
2505244491: 4 4 814 9 95 69 7 9 2 7 9
10917456: 27 8 71 3 55 59 4 8 62
10409799088: 844 805 3 349 9 55 1 7
280983: 1 16 7 5 8 2 3 7 66 67 20
332909422: 3 7 17 71 8 877 6 11 5 4
17499: 6 6 5 4 307 17 40
3395084375: 45 44 95 9 1 747
22993515036725: 19 2 7 65 190 9 36 724
1506114504: 8 7 4 7 8 246 9 1 4 1 82 1
2235273466: 9 3 2 47 6 2 22 734 6 1 5
25156615: 3 8 5 5 363 42 6 632 83
17866649: 84 4 395 514 9
401544: 7 1 8 62 4 43 46
18363214506: 7 7 2 782 6 392 8 35 78
35340: 42 26 3 5 5 93
711531503: 8 6 5 3 8 530 642 8 853
9426965: 88 6 261 8 62
430502730: 2 5 9 703 3 9 8 7 1 66 7 6
10659: 2 8 6 1 4 9 365 9 1 3 57 5
777903204: 3 26 84 12 7 5 7 5 1 4 4 3
321354: 326 3 67 37 9 33
11661: 20 90 1 3 21 87
5289024: 528 83 7 20 7
3814195207: 8 3 5 4 4 97 8 8 800 6 1 6
47396388: 3 82 2 882 5 351 3 89
45191: 928 8 6 5 641
304: 8 19 2
838493145898: 3 835 493 1 4 588 5 16
105296498: 375 79 28 7 2 743 98
922111246: 75 876 2 330 7 5 7 1 3 6
73143515: 69 8 9 8 9 3 8 639 761 5
25263914420: 508 48 635 439 163
14103914: 91 75 116 38 731
271021740033: 4 96 15 6 420 470 33
28833984: 9 1 8 1 686 79 98 28 32
211323894: 161 934 435 8 3
83406960: 260 76 67 7 9
9904924808: 78 6 7 6 9 4 6 3 12 5 4 6
4754: 7 5 96 4 148
2392: 83 3 67 55 146 9 63 9 4
3897: 9 35 32 9 774
60842: 14 97 8 930 58