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:
190: 10 19
has only one position that accepts an operator: between10
and19
. Choosing + would give29
, but choosing*
would give the test value (10 * 19 = 190
).3267: 81 40 27
has two positions for operators. Of the four possible configurations of the operators, two cause the right side to match the test value:81 + 40 * 27
and81 * 40 + 27
both equal3267
(when evaluated left-to-right)!292: 11 6 16 20
can be solved in exactly one way:11 + 6 * 16 + 20
.
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:
156: 15 6
can be made true through a single concatenation:15 || 6 = 156
.7290: 6 8 6 15
can be made true using6 * 8 || 6 * 15
.192: 17 8 14
can be made true using17 || 8 + 14
.
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));
Links
- If you’re new to Advent of Code, it’s an annual event that takes place throughout December, featuring a series of programming puzzles that get progressively more challenging as Christmas approaches.
- Solve Advent of Code 2024 with Deno and Win Prizes!
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