print("""\ 1857 1420 865 663 964 988 189 582 482 1139 173 531 246 878 433 1020 426 1377 943 536 679 55 343 1043 313 1337 167 1262 565 700 733 668 698 797 33 870 217 199 258 173 778 666 77 842 63 18 389 1254 914 640 633 196 517 526 456 754 490 90 159 980 10 1278 793 111 300 1113 459 1197 100 1366 895 1350 567 1143 360 219 393 716 555 1260 557 1161 833 12 88 606 143 517 408 1406 348 1259 33 829 168 457 828 1274 55 568 461 1194 862 1036 363 658 309 238 679 1233 758 1332 123 1133 313 1285 287 648 429 697 320 507 434 229 606 1150 878 1310 443 620 552 1229 63 335 981 744 657 877 847 731 38 1140 981 949 111 968 639 33 613 906 295 1229 623 309 668 970 852 1376 836 433 153 736 623 965 207 459 163 914 104 453 28 529 796 526 191 948 535 1336 676 245 71 701 422 504 156 584 354 600 626 69 949 27 759 1139 731 539 586 756 640 593 63 1224 763 799 548 827 172 1180 396 1027 167 1384 241 999 891 1276 144 1081 972 1065 903 1140 554 53 341 55 898 846 802 1060 79 951 571 579 1000 107 172 573 19 355 564 564 921 501 369 411 382 893 333 135 865 716 77 2 114 796 552 17 425 370 86 1313 903 1367 280 1129 666 275 922 208 316 56 617 363 690 164 824 19 27 253 46 659 462 1281 542 1141 124 879 265 1302 241 890 520 526 983 294 111 42 406 1275 218 24 303 663 734 329 732 67 6 799 318 1382 821 1107 275 276 638 509 324 183 594 1137 94 231 20 1210 575 1092 4 1323 991 1175 949 684 813 420 48 393 299 866 747 471 94 444 438 759 707 328 75 1340 541 1181 507 773 995 195 963 564 728 243 227 361 259 498 675 459 476 321 576 740 404 604 554 44 358 837 526 748 46 1165 145 937 590 698 456 1 397 879 963 750 87 1220 648 667 376 847 677 416 164 617 628 1349 3 600 152 1359 41 1051 637 1038 168 900 924 365 990 313 450 903 702 672 529 404 34 1175 596 872 74 863 14 1102 184 768 117 34 915 1174 758 40 854 261 617 373 829 629 712 18 495 226 971 1238 659 1016 280 1197 809 912 482 1217 737 705 698 520 999 242 866 855 124 1260 115 379 465 1378 480 524 511 1301 637 1 454 1300 761 1049 465 259 554 879 877 1265 606 1114 517 686 143 98 813 406 381 233 424 1384 588 951 864 947 460 649 890 1387 880 780 240 619 929 582 18 169 891 572 330 970 653 377 368 803 119 1357 952 217 957 276 18 623 326 909 590 136 200 816 565 1350 823 514 185 1388 566 1028 940 1034 909 1349 285 835 974 711 307 720 560 1207 593 366 45 1061 324 925 92 714 359 275 738 252 399 1326 139 485 985 786 759 921 744 450 953 968 933 751 54 549 888 621 613 394 248 600 756 1297 603 737 572 515 595 1172 457 805 220 947 774 140 618 1320 8 146 974 153 880 349 510 38 727 611 331 1266 765 896 853 762 718 767 130 417 412 1080 917 1184 257 899 845 1189 452 84 72 307 84 422 798 339 707 164 621 106 305 91 936 944 498 584 928 663 427 729 218 562 872 782 343 630 125 653 203 458 940 331 371 664 888 785 673 167 960 924 258 296 258 965 612 394 670 769 964 858 277 455 75 1249 720 430 198 366 149 10 634 323 170 494 306 289 173 159 904 822 596 1192 355 722 112 1379 331 443 348 1045 927 810 674 1094 265 753 930 916 300 271 953 610 905 27 136 1277 833 1282 461 1101 88 711 967 1101 787 768 131 973 297 1049 869 674 692 568 935 287 612 443 515 447 698 550 577 809 998 963 220 196 254 27 615 303 434 937 883 1303 310 593 562 342 121 968 352 131 271 722 5 830 67 323 431 119 59 748 962 146 82 858 57 221 849 683 892 501 936 1054 782 1286 212 796 539 647 813 1060 291 237 508 431 503 786 175 376 251 20 792 495 883 375 485 248 892 308 259 61 444 1324 621 1053 749 1096 624 451 888 1326 419 686 662 405 225 25 298 1150 255 613 647 848 202 1273 388 511 330 899 50 1089 288 11 565 271 288 669 355 942 731 297 649 226 744 87 429 133 989 902 426 349 686 1102 982 574 961 199 811 1006 678 434 91 891 286 76 867 441 57 1090 131 90 764 1166 785 1357 127 576 334 645 503 701 36 633 194 790 696 348 359 645 11 1293 982 348 657 1357 797 547 461 220 510 1001 430 1281 795 509 194 270 540 1192 22 1035 235 1022 676 915 867 623 456 44 654 1308 214 725 32 29 924 1080 458 1267 674 208 496 148 116 424 244 856 982 399 652 857 728 1381 605 311 788 1267 29 1205 922 944 233 577 612 367 33 1243 566 1173 441 581 115 517 732 525 454 165 634 384 218 26 120 1295 59 324 69 1287 70 1069 974 162 837 469 334 813 62 1174 472 225 684 1322 884 1163 898 1067 697 1001 890 47 780 430 488 535 438 1371 573 992 44 107 242 1183 483 458 273 1001 485 1257 535 650 645 1070 560 269 628 1066 508 902 517 1161 236 1000 626 473 898 566 839 460 757 1068 296 1182 133 1045 424 1059 228 457 347 55 694 998 299 593 443 146 331 900 392 170 131 1273 440 1044 926 1261 765 639 466 331 213 842 596 67 39 465 645 1335 543 13 87 614 908 196 511 310 151 1268 715 1312 99 1128 499 562 480 636 233 1144 728 859 510 1256 438 450 472 952 839 171 568 1007 206 192 111 1249 156 1174 243 465 692 373 679 712 697 1020 819 843 139 269 214 1256 336 487 250 1391 91 290 190 720 791 354 981 1084 6 688 820 952 292 1328 432 298 488 665 934 1188 322 935 146 1040 967 1110 514 1254 924 1160 788 1316 252 409 753 759 952 655 842 917 34 1152 629 163 666 963 383 349 331 1080 964 418 665 1293 715 754 227 1191 546 1123 4 1352 838 227 780 572 885 44 159 1374 264 394 839 811 149 1241 428 720 621 1273 878 601 353 191 824 1386 136 1205 314 507 420 1163 744 1282 290 881 259 1237 798 1121 309 371 801 226 405 804 737 351 588 679 902 232 756 945 127 1317 113 311 111 965 848 319 536 1289 671 639 191 180 98 749 406 697 890 970 105 584 726 1288 224 853 860 360 163 650 695 941 604 717 155 179 994 993 231 437 886 722 184 1088 858 1140 328 1367 895 687 514 1371 730 195 616 1160 557 754 255 993 536 1209 172 934 253 241 972 677 298 114 774 670 991 1053 409 226 74 992 120 773 769 494 344 341 336 5 565 289 902 719 963 1098 125 1199 901 1279 434 516 293 536 851 1074 417 1051 703 1214 17 1053 843 1352 778 289 129 740 198 1076 300 744 533 923 241 598 50 902 783 959 278 383 375 1392 896 300 671 131 924 621 488 799 609 1184 136 877 346 74 295 679 546 382 511 920 152 221 473 47 367 749 590 1048 997 1169 203 1096 458 1001 740 1270 3 279 372 1215 576 365 70 130 303 409 114 1016 490 1176 265 915 920 975 336 730 451 1289 149 836 261 411 79 717 681 276 66 68 249 952 559 1151 22 1160 734 395 918 1334 222 386 180 865 451 1362 615 126 413 179 203 1389 886 193 602 977 130 944 597 1083 516 1222 646 1255 755 934 351 858 705 141 741 966 570 39 851 180 827 419 695 214 653 801 985 802 410 1383 67 1020 987 345 275 911 534 79 749 135 384 1388 582 612 238 1376 546 624 450 894 145 893 156 1339 909 467 257 1046 633 684 980 1339 529 83 485 890 406 550 226 1295 957 471 217 609 529 733 288 552 313 646 217 279 482 44 871 1152 320 654 97 370 142 945 481 421 992 1379 709 174 274 827 348 1195 183 972 520 235 503 1024 161 375 646 832 251 767 653 505 520 180 704 396 653 652 505 1080 507 634 390 1281 959 142 598 663 793 992 514 1199 803 1106 241 609 900 1128 945 989 782 817 263 183 180 283 545 563 499 1281 252 1008 968 435 401 505 464 329 469 1090 378 982 414 1103 672 546 219 773 960 219 385 151 29 402 733 1148 553 243 855 349 211 492 742 635 390 534 684 820 638 701 405 1153 464 482 139 527 632 708 411 1321 681 1382 527 890 526 22 565 26 396 748 118 1248 398 994 875 640 187 618 910 1028 454 1006 732 751 244 1410 696 168 419 79 624 676 692 440 610 882 906 1287 546 1231 669 400 8 462 698 400 208 1237 408 1293 125 890 552 600 428 518 904 525 613 1068 520 174 418 1102 991 1275 573 1154 315 243 446 698 383 430 889 389 498 837 909 92 350 1055 157 750 77 821 800 339 741 54 471 460 337 408 474 720 141 407 920 1082 739 794 339 721 184 274 304 93 989 1400 342 458 995 700 343 580 388 37 365 902 204 60 925 900 517 7 660 135 87 70 446 1305 905 608 525 955 492 902 941 333 603 1393 665 887 398 523 789 1080 964 335 454 826 888 901 94 291 385 782 984 44 397 396 735 1299 888 91 807 865 787 215 642 127 896 760 312 468 873 865 468 321 108 930 210 756 847 759 702 394 440 445 313 1135 568 735 601 871 308 879 333 731 530 116 86 1411 421 596 104 644 134 886 63 933 116 3 54 368 506 977 168 861 793 988 70 1110 253 1336 639 475 669 1408 603 934 969 615 182 1319 184 803 652 1395 488 1383 674 47 336 697 641 1014 484 180 270 639 257 680 305 677 963 434 386 428 111 1174 787 346 222 1105 973 1142 300 14 351 12 279 801 440 1308 815 241 773 988 934 1055 867 71 817 1036 408 339 198 1372 77 565 417 853 85 1261 83 287 198 700 583 1293 631 830 78 493 972 1051 968 1303 224 1056 834 665 452 309 678 664 362 1247 954 902 183 779 35 231 632 347 980 920 969 783 145 65 80 954 143 1224 510 333 564 1346 590 1070 73 1148 114 378 150 259 574 329 179 193 523 1009 751 77 7 1169 646 1385 80 668 597 651 225 329 277 292 920 1316 87 1090 982 1202 810 776 592 373 896 24 422 787 801 369 903 116 110 571 248 442 236 264 681 784 779 92 370 168 247 730 178 1140 431 1249 875 705 385 250 427 73 856 135 543 640 875 1357 401 350 136 535 732 1203 884 330 279 1408 828 910 729 483 947 566 80 266 234 426 591 425 235 178 332 440 51 322 76 391 188 429 619 1280 789 1370 451 1419 422 169 912 676 862 1069 854 630 770 851 268 367 47 190 791 614 974 1359 99 15 379 654 345 1206 477 1144 496 38 414 474 666 322 966 1406 340 634 312 497 215 1323 699 1389 696 936 794 220 117 1182 854 335 762 563 732 1006 502 414 24 1383 990 1031 211 529 417 564 898 444 667 589 600 1017 218 1351 532 125 783 1388 990 262 702 211 289 1217 404 1220 792 62 441 1317 70 490 264 898 192 391 960 663 663 1394 659 638 202 1103 149 666 219 224 400 822 342 1242 584 1356 141 1083 404 1164 653 271 140 960 890 1022 926 1123 709 782 542 403 647 386 869 1127 550 1174 850 476 530 216 781 458 467 886 854 557 949 742 276 926 135 750 735 784 526 141 469 347 854 1358 296 1410 657 307 853 1283 207 867 556 235 217 1342 510 206 14 659 363 1015 295 142 684 235 855 277 30 1371 168 635 392 1137 925 345 595 90 896 755 686 716 74 824 499 1264 425 1114 572 992 822 763 15 452 193 1332 232 306 341 1193 239 720 173 252 209 1365 277 1247 694 752 464 767 298 948 1000 1375 102 888 855 1402 695 892 226 700 650 1179 612 710 881 532 864 925 47 314 510 989 26 734 119 1131 97 942 572 795 940 1038 366 102 572 1052 457 112 918 1214 222 258 501 1342 188 1414 171 518 728 1028 110 475 7 323 417 1119 978 1067 407 242 124 23 455 946 720 935 899 17 452 831 566 613 788 550 183 530 642 945 454 498 474 1008 796 607 128 498 56 1025 895 595 91 1342 973 629 591 858 856 531 989 314 901 632 263 2 783 1296 566 1096 317 529 93 226 51 1263 323 897 606 714 101 1257 459 860 780 763 44 1071 252 301 161 4 58 1399 991 920 573 924 700 1191 831 412 860 81 342 43 658 202 392 596 765 890 562 1041 448 907 843 1215 51 834 254 451 559 1370 44 1044 578 1376 827 725 827 844 165 388 496 517 780 29 910 726 854 335 686 603 750 674 645 67 572 1190 323 1378 79 520 64 95 493 437 450 141 971 99 269 1053 779 670 844 737 151 766 189 1390 683 49 29 263 873 1223 789 1147 787 121 630 515 516 898 421 1342 46 99 996 624 800 978 696 1103 80 1393 986 173 963 1050 600 455 873 536 680 815 883 316 938 1041 885 1281 678 1376 552 153 864 31 202 110 837 1223 764 1343 542 355 734 688 677 768 33 589 220 682 323 1377 137 141 165 212 360 875 845 1036 628 620 633 351 135 643 636 1033 120 885 911 253 759 1242 156 1302 685 740 363 930 266 967 851 358 785 1352 5 1088 931 658 546 417 917 81 143 524 30 1006 986 729 396 54 189 345 501 318 443 1385 409 735 906 1372 860 587 507 1081 625 19 349 1330 729 996 141 605 533 502 126 83 436 200 3 113 561 24 86 1390 487 800 913 1197 767 964 118 1045 451 1270 901 485 333 116 898 953 372 1405 890 292 723 612 179 113 824 477 648 970 504 121 953 1407 578 529 18 1007 558 791 649 386 691 484 20 396 467 1199 583 742 145 1026 255 1294 32 297 374 326 584 961 127 967 538 278 169 685 515 707 646 334 712 54 602 788 649 843 690 989 915 667 124 382 969 1097 96 1289 648 1068 713 312 57 894 614 606 288 139 703 1241 553 834 8 613 204 190 28 170 973 464 581 136 328 518 558 939 820 1395 119 934 792 933 944 1359 755 1382 616 568 101 567 776 171 588 1278 361 896 138 133 381 254 635 205 963 800 485 1178 349 1347 34 1255 692 314 616 1266 538 1234 589 96 219 607 655 189 667 131 123 808 449 1317 665 1307 39 519 526 1038 31 521 426 751 475 464 746 873 977 417 814 264 356 360 747 285 997 432 570 102 642 630 451 921 650 510 78 493 951 1240 280 291 403 1037 339 802 611 1415 817 328 625 949 426 418 600 708 58 535 400 658 196 589 812 515 568 79 136 633 77 322 529 1258 726 1248 499 206 593 238 906 873 614 25 819 931 428 508 604 992 456 553 679 844 538 430 944 361 332 1099 485 192 625 571 603 1050 224 870 845 1383 844 139 774 764 32 453 629 1388 594 311 898 194 910 977 348 1093 860 462 335 1035 419 1306 123 15 303 298 783 396 779 943 245 1366 244 1154 872 297 739 149 346 1284 407 1030 500 488 363 98 630 1361 706 1400 596 244 407 481 388 1068 83 567 767 1246 51 815 168 671 548 999 301 16 482 520 655 1110 712 214 996 1172 764 664 193 1095 848 986 766 1004 121 1118 266 647 597 1293 244 174 41 1403 817 802 837 8 431 629 133 151 107 745 851 187 174 609 886 160 753 141 448 1214 890 494 561 195 472 1185 272 987 678 350 958 312 789 906 635 1277 458 1337 413 1223 770 445 133 1391 85 527 155 353 825 487 320 946 607 918 222 1010 543 910 664 1005 378 1005 239 803 267 273 360 228 57 180 691 310 41 852 713 234 526 171 705 255 972 1077 84 189 662 1108 582 646 430 755 679 55 274 5 361 1195 937 1172 538 718 542 61 496 1081 66 300 170 263 840 298 821 963 337 808 195 833 486 11 871 227 743 20 602 109 535 752 733 317 975 65 978 552 331 335 880 385 770 811 645 630 767 618 576 342 420 941 283 108 451 683 26 1222 54 483 587 959 1 1070 399 1157 833 1262 887 513 581 593 550 172 108 1226 188 574 243 691 876 1136 609 1128 67 1231 475 1341 16 1280 367 1357 169 344 221 319 165 911 431 1210 208 605 462 674 411 552 637 1176 918 1033 820 880 47 1046 228 693 936 665 227 715 667 1123 478 404 744 1035 62 28 446 897 273 647 385 1254 806 118 159 1405 88 684 955 840 35 148 674 400 739 88 936 594 349 102 381 166 966 1123 927 1078 783 1138 209 934 942 316 764 418 842 223 529 138 847 463 862 1345 440 380 286 1311 3 324 330 1013 622 207 500 303 140 665 92 188 289 247 583 65 88 149 397 923 552 10 372 1214 868 741 223 154 968 951 949 183 172 639 841 557 984 1131 201 18 887 593 915 447 282 551 951 672 268 459 902 774 539 1066 603 202 155 398 532 295 911 855 232 326 938 230 378 868 125 214 363 925 713 118 925 1237 834 1112 333 467 815 932 470 774 186 999 589 849 734 777 455 940 634 480 769 17 698 171 240 998 669 603 650 16 23 315 631 1156 309 1126 357 1259 202 1122 938 444 331 263 612 127 844 998 624 661 396 1035 109 762 566 914 860 654 642 1013 663 1370 313 840 481 1004 336 85 777 166 216 671 277 1105 470 56 220 408 440 1211 510 1018 199 933 625 151 795 332 873 102 482 686 155 1102 316 1353 506 637 902 1356 866 1211 819 605 464 1215 589 504 569 959 490 562 29 251 806 1174 671 773 411 822 852 841 640 226 711 982 328 472 84 247 398 1103 687 47 339 479 271 444 110 47 200 1397 233 1144 245 428 303 631 54 73 483 96 949 512 991 802 594 311 800 1203 694 285 952 1221 193 1271 886 1368 346 92 75 10 289 1191 852 355 383 732 762 627 914 52 761 1405 461 1309 988 713 734 1323 271 1281 275 1264 525 381 461 1215 122 408 65 1249 922 635 746 1132 106 896 841 485 905 83 670 966 200 488 210 862 443 737 338 988 878 1371 816 689 12 835 542 1368 661 563 596 857 821 1044 869 1377 463 586 616 881 245 1145 514 587 554 107 499 372 654 522 385 1248 587 691 529 30 """ )