A positive integer $a$ is given. Baron Munchausen claims that he knows such a positive integer $n$ that if one multiplies $n$ by $a$, the sum of its digits decreases $a$ times. In other words, $S(an) = S(n)/a$, where $S(x)$ denotes the sum of digits of the number $x$. 

Find out if what Baron told can be true.


-----Input-----

The only line contains a single integer $a$ ($2 \le a \le 10^3$).


-----Output-----

If there is no such number $n$, print $-1$.

Otherwise print any appropriate positive integer $n$. Your number must not consist of more than $5\cdot10^5$ digits. We can show that under given constraints either there is no answer, or there is an answer no longer than $5\cdot10^5$ digits.


-----Examples-----
Input
2

Output
6

Input
3

Output
6669

Input
10

Output
-1

Difficulty: VERY_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
tabela = '\n3 11 1 1 2 1 2\n6 1 4 2 11 3 20\n7 2 7 9 1 7 6\n9 11 40 1 2 40 0\n11 1 7 6 1 6 3\n12 2 13 2 11 12 1\n13 1 9 15 1 8 30\n14 1 10 12 11 9 36\n15 11 14 2 2 14 4\n17 2 14 9 2 13 27\n18 1 34 4 1 33 1\n19 1 15 18 1 14 9\n21 1 17 10 2 14 8\n22 1 12 6 1 10 3\n23 1 11 3 11 9 27\n24 1 39 6 1 38 0\n26 1 16 18 2 15 36\n27 11 67 4 2 67 0\n28 1 24 18 11 22 36\n29 1 15 6 11 19 0\n30 2 16 1 11 15 2\n31 11 23 27 1 22 18\n33 2 66 1 11 65 2\n34 1 25 39 2 24 30\n35 1 22 27 2 20 18\n36 1 48 1 1 47 6\n37 11 22 18 11 20 0\n38 2 29 18 2 28 33\n39 11 80 11 2 77 1\n41 11 39 3 2 36 15\n42 11 30 5 1 30 4\n43 2 33 18 1 31 9\n44 2 42 9 1 41 0\n45 11 102 2 2 102 0\n46 1 41 36 11 39 18\n47 2 40 27 1 41 6\n48 11 74 3 2 74 0\n49 1 37 18 2 35 33\n51 1 37 2 1 35 13\n52 11 49 6 1 48 3\n53 11 47 36 11 35 18\n54 1 106 5 1 105 0\n55 1 28 9 1 26 0\n56 1 68 24 1 67 36\n57 11 39 4 1 33 23\n58 11 48 36 2 32 36\n59 11 43 9 1 47 30\n60 1 32 2 1 31 4\n61 11 45 9 2 44 0\n62 11 39 18 11 44 18\n63 1 143 7 1 142 0\n65 1 34 15 1 28 12\n66 11 67 2 11 66 4\n67 11 52 27 1 47 9\n68 1 51 18 11 54 30\n69 2 47 8 1 42 31\n70 1 34 3 1 28 24\n71 11 61 36 11 63 18\n72 1 84 5 1 83 3\n73 1 36 9 1 29 27\n74 11 41 18 11 38 0\n75 11 114 3 2 114 0\n76 11 75 30 1 66 6\n77 1 39 12 1 34 15\n78 1 159 4 1 153 14\n79 2 101 21 2 89 33\n81 11 174 3 2 174 0\n82 1 119 9 11 115 0\n83 1 64 9 2 86 12\n84 1 60 7 1 54 20\n85 1 41 6 1 51 36\n86 1 79 24 11 70 21\n87 2 59 2 1 54 37\n88 1 122 9 1 120 0\n89 11 64 27 1 59 18\n90 2 406 1 11 405 0\n91 1 45 9 1 40 18\n92 1 91 30 11 83 6\n93 11 111 29 2 148 31\n94 1 88 12 2 104 3\n95 1 46 3 11 58 27\n96 1 100 1 1 99 5\n97 1 49 30 2 58 27\n98 11 91 9 1 66 36\n99 2 1782 1 11 1781 0\n101 1 50 15 1 48 3\n102 11 76 16 1 67 5\n103 1 53 33 2 85 33\n104 1 117 3 1 111 24\n105 1 72 2 2 69 16\n106 11 74 36 11 62 27\n107 2 92 18 1 75 0\n108 1 185 5 1 184 0\n109 1 56 27 1 63 27\n110 1 52 6 1 51 3\n111 11 58 10 11 57 8\n112 1 151 9 1 145 18\n113 1 58 21 1 71 18\n114 11 76 2 1 70 25\n115 1 57 21 2 70 36\n116 11 77 9 1 44 36\n117 1 264 4 1 263 3\n118 2 108 9 1 100 18\n119 2 134 12 11 126 27\n120 2 122 2 11 121 1\n121 1 109 3 11 108 6\n122 2 146 30 1 108 3\n123 11 155 7 11 151 17\n124 11 70 9 11 90 12\n126 1 228 2 1 227 4\n127 1 65 18 11 105 36\n129 1 93 13 2 77 32\n130 1 64 24 1 59 3\n131 1 67 30 2 144 15\n132 1 134 1 1 132 11\n133 1 65 21 2 117 12\n134 1 97 36 11 87 27\n135 11 281 3 2 281 4\n136 11 155 18 1 153 0\n137 1 68 24 1 62 12\n138 11 97 4 2 93 20\n139 1 71 24 11 115 33\n140 1 65 3 1 59 24\n141 1 99 5 1 97 7\n142 11 133 3 1 110 36\n143 1 69 18 1 65 9\n144 11 164 1 2 164 3\n145 1 72 27 1 94 9\n146 1 69 15 1 62 21\n147 1 108 31 2 191 28\n148 11 150 9 11 147 0\n149 2 107 9 1 127 21\n150 11 150 2 2 150 4\n151 1 117 18 1 146 12\n152 1 139 27 1 161 36\n153 11 329 4 1 329 37\n154 1 76 27 1 71 0\n155 11 120 21 11 85 18\n156 2 314 2 11 311 4\n157 11 180 33 11 172 21\n158 1 191 24 1 179 21\n159 11 101 23 1 122 1\n161 1 181 9 1 108 18\n162 1 323 5 1 321 6\n163 2 255 18 11 245 27\n164 1 159 24 1 155 3\n165 11 331 1 11 330 5\n166 1 178 15 1 105 9\n167 1 157 33 11 180 24\n168 11 226 7 1 223 11\n169 1 225 9 11 218 36\n170 1 118 18 1 115 0\n171 1 343 1 11 342 8\n172 1 163 9 11 154 27\n173 11 166 21 1 171 39\n174 1 122 31 2 117 23\n175 1 83 15 1 77 12\n176 1 238 9 2 237 0\n177 1 130 38 2 228 32\n178 2 119 9 1 113 9\n179 1 91 36 1 116 27\n180 1 326 1 1 325 4\n181 1 92 9 11 124 9\n182 1 88 24 1 83 3\n183 1 125 7 2 236 34\n184 1 249 9 11 245 0\n185 11 95 9 11 93 9\n186 1 158 11 11 100 25\n187 11 169 6 1 218 27\n188 2 133 27 2 162 36\n189 1 603 5 1 599 10\n190 11 130 18 1 124 9\n191 11 305 15 11 300 12\n192 11 386 1 2 386 11\n193 11 214 15 2 250 36\n194 1 221 30 1 252 0\n195 1 394 7 1 388 11\n196 2 147 36 11 133 0\n197 11 220 18 1 214 27\n198 11 714 2 11 713 3\n199 1 145 9 11 192 36\n201 2 134 10 1 134 26\n202 1 95 15 1 92 3\n203 1 199 24 1 186 21\n204 1 147 14 2 128 16\n205 1 195 21 11 190 6\n206 2 187 27 1 87 27\n207 1 421 4 11 420 14\n208 11 281 18 2 278 0\n209 1 101 33 1 185 6\n210 1 144 10 2 141 8\n211 11 195 3 2 183 33\n212 1 262 21 1 254 15\n213 2 284 7 2 283 5\n214 1 319 15 11 314 12\n215 2 160 27 1 137 18\n216 1 346 5 1 345 10\n217 2 248 27 1 177 27\n218 1 196 30 1 240 12\n219 11 754 9 11 750 0\n220 1 101 6 1 99 3\n221 11 238 12 1 237 6\n222 11 113 5 11 111 13\n223 2 297 18 1 245 24\n224 1 307 27 1 301 0\n225 11 255 4 2 255 0\n226 1 208 27 11 200 18\n227 2 253 33 1 264 21\n228 1 153 4 11 149 17\n229 2 265 24 1 309 27\n230 2 158 18 1 153 9\n231 11 311 10 2 308 8\n232 2 212 24 1 204 30\n233 11 264 9 1 314 0\n234 2 528 7 11 527 6\n235 1 117 36 2 205 27\n236 2 322 36 2 307 36\n237 1 387 2 1 383 22\n238 11 313 30 1 325 39\n239 2 563 18 2 558 0\n240 1 364 6 1 363 0\n241 2 274 21 1 107 15\n242 1 123 36 11 208 36\n243 11 496 8 2 496 14\n244 11 167 18 2 211 36\n245 1 164 9 1 107 30\n246 11 355 11 11 352 1\n247 1 229 39 11 267 39\n248 1 282 15 11 276 9\n249 2 337 19 1 326 35\n251 1 230 18 2 227 0\n252 1 415 5 1 413 5\n253 1 123 36 2 219 27\n254 2 233 12 2 278 30\n255 1 166 1 1 164 11\n257 1 288 12 11 287 33\n258 2 181 11 1 158 34\n259 1 262 9 1 256 9\n260 1 119 9 1 113 18\n261 11 518 4 2 518 6\n262 11 410 9 11 406 9\n263 1 242 21 1 285 39\n264 1 214 2 1 212 13\n265 1 280 24 1 267 39\n266 2 245 33 1 295 6\n267 1 192 14 2 342 23\n268 1 377 27 11 346 27\n269 11 484 27 1 484 0\n270 2 664 2 11 663 5\n271 11 383 18 11 378 0\n272 2 367 9 11 364 9\n273 1 274 1 1 268 17\n274 1 125 6 1 118 30\n275 1 125 3 1 123 6\n276 1 197 14 11 350 32\n277 1 305 21 1 237 21\n278 2 255 18 2 309 0\n279 11 572 1 11 569 12\n280 1 193 18 1 187 9\n281 2 443 21 11 437 6\n282 1 193 13 1 367 25\n283 1 197 27 2 233 33\n284 11 274 39 1 395 6\n285 1 196 26 2 192 4\n286 1 130 3 1 125 24\n287 11 324 9 1 320 9\n288 11 648 2 2 648 0\n289 2 329 36 2 321 0\n290 2 200 27 1 195 0\n291 1 392 5 1 389 7\n292 1 134 6 1 126 30\n293 2 270 24 11 252 39\n294 1 206 38 11 387 23\n295 1 332 21 2 327 15\n296 2 546 9 1 544 9\n297 2 1605 1 11 1604 2\n298 11 198 18 1 193 27\n299 2 270 21 11 260 33\n300 2 152 1 11 151 2\n301 1 375 15 1 370 12\n302 2 374 12 2 369 15\n303 2 607 1 11 606 2\n304 1 341 3 1 400 36\n305 11 273 9 2 272 0\n306 1 604 4 1 603 2\n307 11 356 9 11 353 9\n308 1 143 15 1 137 12\n309 1 489 2 1 486 22\n310 1 263 9 11 226 33\n311 11 311 12 11 310 6\n312 2 626 1 11 623 2\n313 11 284 33 2 405 27\n314 11 422 18 11 419 0\n315 11 710 1 2 710 2\n316 1 309 9 1 381 9\n317 1 507 30 2 519 24\n318 1 266 19 1 253 29\n319 1 372 30 11 417 36\n321 11 428 4 2 426 5\n322 2 297 15 2 225 0\n323 1 377 18 11 415 18\n324 1 613 4 1 612 12\n325 1 149 9 1 143 18\n326 1 502 3 11 513 6\n327 1 445 29 2 439 1\n328 1 310 15 1 305 12\n329 1 302 33 1 348 33\n330 2 661 1 11 660 2\n331 11 451 27 1 512 21\n332 1 481 9 1 480 0\n333 11 1499 1 2 1499 2\n334 11 380 27 2 370 18\n335 2 234 9 1 213 18\n336 1 451 8 1 446 19\n337 1 294 12 11 301 33\n338 1 302 15 11 296 39\n339 2 228 11 1 222 37\n340 1 154 3 11 221 36\n341 2 434 18 1 483 27\n342 1 685 1 11 684 13\n343 1 149 18 2 372 27\n344 1 221 9 1 290 15\n345 2 246 34 11 230 38\n346 1 402 15 11 404 39\n347 11 324 15 11 552 39\n348 11 462 19 1 469 29\n349 11 398 39 1 313 3\n350 1 161 18 1 155 9\n351 2 679 6 2 677 11\n352 1 474 9 1 473 0\n353 11 473 18 2 469 9\n354 1 470 5 1 463 19\n355 11 272 39 1 394 6\n356 11 242 18 1 236 9\n357 2 487 34 2 470 29\n358 11 242 18 11 313 30\n359 11 451 36 1 450 0\n360 1 466 4 1 465 3\n361 2 262 36 1 173 0\n362 11 491 18 1 480 18\n363 2 503 11 1 515 10\n364 1 167 15 1 161 12\n365 1 165 3 1 158 33\n366 1 256 35 2 484 26\n367 2 497 27 1 493 9\n368 1 416 18 1 491 9\n369 11 832 2 11 829 1\n370 11 188 9 11 186 9\n371 1 410 33 11 417 21\n372 1 622 8 11 618 24\n373 1 665 15 2 582 6\n374 1 301 24 1 296 12\n375 1 566 6 1 565 0\n376 1 591 24 1 496 36\n377 1 429 27 11 436 9\n378 1 933 11 1 929 1\n379 1 587 18 1 584 0\n380 1 173 15 2 246 36\n381 1 495 35 1 487 4\n382 11 530 30 11 522 15\n383 2 341 6 1 339 3\n384 1 773 2 1 772 4\n385 1 178 21 1 173 6\n386 1 432 36 1 423 9\n387 1 719 1 1 718 7\n388 11 256 18 2 252 0\n389 1 609 3 11 516 9\n390 11 783 11 2 780 1\n391 1 575 27 2 746 30\n392 1 277 27 11 345 30\n393 11 523 4 2 517 23\n394 2 444 3 11 435 15\n395 1 387 18 1 374 36\n396 11 1020 1 11 1019 6\n397 11 632 9 1 619 18\n398 1 680 21 11 721 36\n399 11 601 11 11 895 6\n401 2 549 36 2 534 18\n402 11 284 26 1 264 4\n403 1 637 33 11 712 0\n404 1 184 9 1 180 9\n405 11 822 5 2 822 0\n406 11 573 18 1 518 18\n407 11 818 9 11 815 0\n408 1 530 23 1 523 16\n409 2 460 33 2 451 12\n410 2 382 3 11 381 6\n411 11 473 13 11 472 5\n412 1 189 12 2 358 39\n413 1 467 18 1 368 18\n414 1 800 4 1 799 1\n415 2 308 36 1 428 18\n416 2 649 3 11 647 15\n417 11 518 8 11 514 25\n418 1 191 6 1 369 24\n419 1 471 21 2 464 15\n420 11 283 5 1 283 4\n421 11 656 24 1 564 0\n422 1 197 36 2 375 0\n423 11 846 4 11 845 2\n424 1 444 18 1 437 18\n425 2 288 9 11 285 0\n426 1 285 4 1 555 34\n427 2 478 15 2 474 3\n428 11 409 15 2 444 33\n429 2 1719 5 2 1715 1\n430 2 373 33 1 305 0\n431 1 542 36 1 523 36\n432 2 689 1 11 688 9\n433 2 491 9 1 667 36\n434 1 416 3 1 308 27\n435 1 290 25 1 279 32\n436 2 287 9 1 376 33\n437 2 492 12 1 582 9\n438 1 1005 10 1 997 11\n439 1 536 21 11 627 0\n440 2 395 9 1 394 0\n441 1 898 2 1 896 4\n442 1 526 36 1 614 9\n443 2 965 12 1 812 3\n444 11 225 7 11 222 11\n445 11 409 39 2 296 36\n446 11 499 3 1 493 33\n447 1 604 10 2 882 36\n448 1 608 27 1 602 0\n449 1 210 18 2 400 0\n450 11 1014 1 2 1014 1\n451 1 757 9 1 755 0\n452 1 708 3 1 606 9\n453 1 667 8 11 660 31\n454 2 427 30 1 294 18\n455 1 208 12 1 203 15\n456 2 612 7 11 605 35\n457 11 817 21 1 810 6\n458 1 526 9 2 394 36\n459 2 938 1 11 937 26\n460 1 211 9 1 306 18\n461 1 517 15 11 503 30\n462 11 623 23 11 618 4\n463 11 416 21 2 506 39\n464 1 526 21 1 514 24\n465 11 265 17 1 383 28\n466 1 318 36 1 516 15\n467 2 712 18 11 703 18\n468 1 1056 1 1 1055 5\n469 11 677 36 1 707 27\n470 11 319 9 2 317 0\n471 11 574 17 1 350 14\n472 11 531 15 1 521 30\n473 1 702 18 1 697 9\n474 1 882 4 1 877 26\n475 1 430 24 2 425 12\n476 11 621 36 11 443 0\n477 11 1021 16 11 1016 0\n478 2 1679 18 11 1672 9\n479 1 483 21 1 711 18\n480 11 723 3 2 723 0\n481 1 490 18 1 484 0\n482 2 546 30 11 637 36\n483 1 669 7 1 668 5\n484 1 439 24 2 431 30\n485 1 435 18 2 434 36\n486 1 971 8 1 970 5\n487 1 861 9 11 865 27\n488 11 760 3 2 759 6\n489 2 329 22 11 318 35\n490 1 332 18 11 428 33\n491 2 565 30 1 424 39\n492 11 620 13 11 615 11\n493 11 703 9 1 723 12\n494 1 227 9 2 441 0\n495 11 4456 1 2 4456 1\n496 11 559 27 11 547 36\n497 11 426 39 11 313 18\n498 2 349 28 1 654 28\n499 1 766 3 2 760 24\n501 1 340 11 1 337 13\n502 1 227 3 2 337 0\n503 1 563 27 2 776 0\n504 11 828 4 11 827 1\n505 1 231 18 1 228 0\n506 1 233 33 1 449 6\n507 1 705 38 11 695 4\n508 2 802 39 1 899 21\n509 1 786 24 11 780 12\n510 2 336 29 1 355 10\n511 1 628 21 1 741 9\n513 2 894 1 2 893 6\n514 2 461 9 11 572 0\n515 2 460 3 1 223 39\n516 2 662 20 1 717 34\n517 1 470 30 2 688 9\n518 2 1042 18 2 1036 0\n519 2 1101 6 2 1098 6\n520 2 467 15 11 464 3\n521 1 236 9 1 342 18\n522 1 1063 1 1 1061 4\n523 1 718 27 11 836 9\n524 1 699 9 2 457 33\n525 1 355 13 2 351 5\n526 1 940 6 1 937 3\n527 2 611 30 11 804 3\n528 2 425 1 2 423 14\n529 2 943 12 11 1050 36\n530 11 387 9 1 540 36\n531 1 1069 4 1 1068 1\n532 2 478 27 1 227 36\n533 2 596 15 1 556 12\n534 11 374 25 1 686 22\n535 1 568 33 1 669 27\n536 11 742 9 1 573 33\n537 2 717 7 1 716 20\n538 11 727 36 2 838 3\n539 2 483 9 1 233 27\n540 1 1045 8 1 1044 0\n541 11 845 27 1 953 36\n542 11 1509 3 11 1505 15\n543 1 729 5 1 717 34\n544 1 731 9 11 845 24\n545 1 378 36 1 365 27\n546 2 1096 10 2 1090 8\n547 2 969 21 2 961 15\n548 1 254 36 1 246 0\n549 1 1112 2 2 1111 39\n550 1 249 9 1 247 0\n551 11 668 18 1 409 18\n552 11 765 26 2 760 7\n553 1 1017 24 11 1038 12\n554 1 815 33 11 822 21\n555 11 281 11 11 279 7\n556 11 500 6 1 862 21\n557 1 758 36 11 624 0\n558 11 1093 2 11 1092 5\n559 1 523 18 11 470 27\n560 1 627 15 1 621 12\n561 2 783 8 2 775 34\n562 1 880 21 11 491 33\n563 1 650 12 1 646 6\n564 11 744 4 2 744 5\n565 11 505 15 2 505 3\n566 11 493 9 1 604 36\n567 1 1299 11 1 1295 6\n568 11 952 18 1 780 36\n569 1 887 21 2 879 24\n570 11 382 4 1 376 23\n571 1 511 30 1 380 27\n572 1 257 3 1 251 24\n573 1 391 11 11 757 26\n574 1 651 39 11 685 6\n575 1 517 9 11 384 9\n576 1 5173 1 11 5172 9\n577 2 643 9 2 764 27\n578 1 772 9 11 656 3\n579 11 387 1 1 382 26\n580 1 268 24 11 385 18\n581 1 1174 27 2 1282 39\n582 2 1168 6 1 1167 12\n583 1 1126 3 1 843 0\n584 2 526 18 2 518 18\n585 11 1317 1 2 1317 5\n586 1 913 9 2 912 0\n587 2 903 30 1 675 3\n588 2 399 10 11 385 35\n589 11 526 12 11 774 36\n590 1 403 36 11 392 18\n591 2 889 10 1 889 17\n592 1 1090 12 1 1087 6\n593 1 663 36 11 527 0\n594 11 2293 5 11 2292 0\n595 11 1096 9 2 998 9\n596 1 661 6 2 520 24\n597 11 738 17 1 442 5\n598 11 669 24 2 798 9\n599 1 737 3 11 725 0\n600 1 303 2 1 302 4\n601 2 798 27 1 938 3\n602 11 945 27 11 936 18\n603 1 1360 9 1 1357 7\n604 1 892 9 2 1032 18\n605 1 277 24 11 532 33\n606 11 974 11 11 970 4\n607 1 819 36 2 813 0\n608 11 952 15 2 942 30\n609 2 809 1 1 808 20\n610 1 553 33 11 407 18\n611 1 549 9 1 1085 9\n612 1 1147 7 1 1146 4\n613 11 939 9 11 937 0\n614 1 1341 12 1 1337 15\n615 11 617 2 11 612 28\n616 2 551 3 2 545 24\n617 11 1107 30 11 1098 15\n618 11 769 22 1 893 20\n619 1 1114 30 1 1106 15\n620 11 465 18 11 340 36\n621 1 1248 5 11 1247 20\n622 11 620 9 2 785 27\n623 11 1153 39 1 976 18\n624 11 1253 17 2 1250 4\n626 1 432 27 2 686 33\n627 2 761 31 2 747 32\n628 1 559 6 1 275 6\n629 2 880 18 2 870 36\n630 1 1420 1 1 1419 4\n631 1 1029 27 2 1164 18\n632 1 771 33 1 758 21\n633 1 744 2 1 1117 6\n634 11 932 12 1 1056 30\n635 2 569 6 1 706 6\n636 11 996 6 2 1033 11\n637 11 718 39 2 569 21\n638 11 575 18 2 1075 27\n639 2 1302 8 2 1301 9\n641 2 1004 3 11 851 18\n642 2 869 29 2 857 37\n643 11 717 33 2 830 36\n644 1 299 3 1 438 18\n645 11 829 25 1 823 2\n646 2 1196 39 1 1117 24\n647 2 1030 18 2 886 0\n648 1 1198 9 1 1197 8\n649 2 1155 9 11 1149 27\n650 1 293 6 1 287 21\n651 1 873 11 2 928 16\n652 2 1013 39 11 1000 24\n653 1 881 9 2 873 27\n654 1 880 37 1 1303 36\n655 1 583 6 2 586 12\n656 11 735 27 11 730 0\n657 11 1394 5 11 1390 10\n658 1 727 9 1 719 36\n659 1 734 33 2 726 39\n660 11 662 2 11 661 4\n661 1 453 36 1 729 39\n662 2 739 12 2 737 6\n663 1 448 20 11 877 35\n664 2 1123 15 11 1237 9\n665 1 746 18 2 587 36\n666 11 1500 2 11 1499 4\n667 1 909 27 2 874 27\n668 1 755 24 1 1040 15\n669 11 905 35 1 1331 27\n670 2 873 27 1 765 21\n671 1 1242 30 2 1371 24\n672 1 901 13 1 896 14\n673 2 904 27 1 890 27\n674 2 1055 27 2 1049 0\n675 11 1075 4 2 1075 3\n676 2 908 36 1 1046 27\n677 1 756 24 2 1051 6\n678 1 902 5 2 454 14\n679 1 1674 18 2 1671 0\n680 11 763 30 2 750 33\n681 1 918 22 11 902 20\n682 1 981 27 2 974 9\n683 11 1349 18 11 1339 36\n684 2 1371 3 11 1369 4\n685 1 309 9 1 302 27\n686 1 1077 21 2 1055 6\n687 1 924 20 1 917 7\n688 1 806 6 2 872 18\n689 1 1076 33 1 1218 24\n690 11 449 2 2 445 19\n691 2 1072 6 11 1229 24\n692 2 796 18 11 597 36\n693 2 3119 1 11 3118 3\n694 1 913 36 2 791 18\n695 2 623 21 2 770 21\n696 1 917 38 1 910 1\n697 2 1069 39 11 776 21\n698 2 1095 24 2 1241 15\n699 11 1399 21 11 1388 33\n700 1 317 12 1 311 15\n701 1 620 9 2 938 0\n702 11 1187 5 11 1186 1\n703 1 607 9 1 1200 27\n704 1 945 9 1 943 0\n705 1 468 7 1 465 8\n706 2 949 36 2 626 24\n707 11 815 36 11 803 27\n708 1 967 28 2 1395 33\n709 11 806 39 2 1090 3\n710 1 600 18 11 659 0\n711 11 1414 9 11 1411 7\n712 2 640 27 11 630 27\n713 1 1294 6 1 1127 33\n714 1 1433 12 2 1428 12\n715 1 322 6 1 317 21\n716 1 643 15 2 625 39\n717 2 1510 15 2 1508 0\n718 2 1257 24 11 1251 3\n719 2 1401 18 1 1395 18\n720 1 814 5 1 813 3\n721 2 1294 36 1 1280 27\n722 2 814 6 2 954 36\n723 1 1211 20 1 1204 13\n724 11 486 18 1 959 27\n725 11 648 6 2 481 18\n726 1 1004 10 1 1001 2\n727 11 811 21 2 802 6\n728 2 653 18 2 647 9\n729 11 1470 1 2 1470 4\n730 1 333 27 1 326 9\n731 2 1146 3 11 1289 39\n732 1 499 25 2 974 31\n733 11 1209 30 1 1240 39\n734 1 507 18 1 649 39\n735 11 979 7 1 978 29\n736 11 1148 6 2 1144 21\n737 11 1021 27 1 637 9\n738 11 1753 14 11 1749 5\n739 1 502 18 1 977 36\n740 11 375 18 11 372 0\n741 11 1484 3 11 1479 21\n742 11 807 15 1 500 27\n743 2 988 27 1 1312 6\n744 11 832 16 1 1237 23\n745 2 667 6 11 495 36\n746 1 836 36 2 660 9\n747 1 1413 25 1 1406 8\n748 2 895 36 11 995 18\n749 1 1185 21 1 1009 27\n750 2 1128 3 11 1127 0\n751 1 1031 18 11 1137 33\n752 2 1344 30 1 1340 6\n753 2 949 37 2 940 14\n754 11 1011 18 11 1007 0\n755 11 1122 36 11 918 36\n756 2 1858 3 11 1857 0\n757 11 1711 18 11 1506 36\n758 2 1018 36 11 677 6\n759 2 1295 38 11 2083 20\n760 1 514 27 11 670 33\n761 1 1197 15 1 1365 33\n762 1 1607 15 11 1525 0\n763 11 1061 36 1 1204 39\n764 11 1651 36 11 1644 9\n765 2 1552 1 2 1551 2\n766 11 684 9 2 842 36\n767 11 1197 21 2 1529 27\n768 2 1925 2 11 1924 1\n769 11 1371 15 2 1371 12\n770 1 346 3 1 341 24\n771 11 1031 16 1 1029 26\n772 2 673 6 2 492 36\n773 2 1256 18 2 1251 18\n774 1 1398 20 1 1395 5\n775 1 871 27 11 862 9\n776 1 520 27 2 1031 18\n777 1 784 13 1 778 5\n778 1 1215 21 1 1208 33\n779 2 1699 24 2 1687 21\n780 1 1564 4 1 1558 14\n781 2 1476 3 11 1299 18\n782 2 947 9 2 942 27\n783 2 1564 19 11 1562 12\n784 1 1408 27 1 1217 36\n785 1 353 15 11 874 12\n786 2 1060 5 1 1558 30\n787 2 1388 33 2 1554 9\n788 2 1584 36 1 1402 6\n789 11 1055 19 1 1053 20\n790 1 764 6 2 947 24\n791 1 1952 36 11 1937 9\n792 11 1785 5 11 1784 3\n793 11 1023 18 1 1415 36\n794 1 742 12 1 923 30\n795 11 452 1 1 643 17\n796 11 648 12 11 1133 15\n797 2 1104 9 2 1277 39\n798 11 1804 30 11 1795 3\n799 11 936 21 1 1486 6\n801 11 1521 10 2 1516 19\n802 11 1433 9 11 1078 0\n803 11 716 3 11 709 33\n804 1 560 16 11 516 32\n805 1 1084 18 1 1245 24\n806 11 1255 6 1 1178 12\n807 1 549 26 11 1069 20\n808 2 724 15 2 720 3\n809 2 1093 36 2 899 18\n810 2 1730 7 11 1729 2\n811 1 1089 27 2 1086 0\n812 2 1046 36 2 865 21\n813 2 4065 1 2 4064 5\n814 1 1637 18 1 1631 0\n815 11 561 36 1 711 30\n816 11 1052 22 2 1044 14\n817 1 1508 30 1 1492 33\n818 1 1278 27 1 1268 36\n819 9 3279 2 9 3276 8\n820 1 1145 9 11 1141 0\n821 11 1647 18 2 1637 27\n822 11 1022 38 11 1016 1\n823 2 1113 36 1 1263 24\n824 11 1659 36 1 1651 9\n825 11 3302 2 11 3301 1\n826 11 1295 33 2 1290 39\n827 2 1269 9 2 1449 36\n828 2 1595 6 2 1594 6\n829 11 558 18 1 547 36\n830 11 807 30 1 598 9\n831 11 1854 12 2 1235 7\n832 2 1298 3 11 1295 15\n833 11 1449 30 2 1525 33\n834 2 1728 39 11 1722 3\n835 11 748 15 2 748 3\n836 2 748 9 1 371 18\n837 2 1853 5 2 1852 3\n838 2 1683 27 11 1680 0\n839 2 1425 3 2 1216 27\n840 1 565 7 1 559 20\n841 2 1111 18 11 935 39\n842 1 1502 3 2 1309 39\n843 2 1191 37 2 1768 21\n844 2 941 12 11 750 21\n845 1 945 9 11 942 0\n846 1 1714 5 1 1713 10\n847 2 759 9 11 754 9\n848 1 879 6 1 873 30\n849 1 1161 11 1 1159 4\n850 11 573 18 1 564 27\n851 1 1959 24 2 1954 12\n852 2 1136 37 2 1125 14\n853 11 1485 21 11 1474 15\n854 11 1286 9 2 1137 9\n855 11 1712 2 11 1710 7\n856 1 1269 18 11 1442 0\n857 1 1151 18 1 1146 0\n858 11 3435 4 11 3429 14\n859 2 767 12 1 379 39\n860 1 557 27 2 602 9\n861 2 1236 10 11 1227 29\n862 2 1280 18 1 1483 21\n863 1 769 27 1 575 36\n864 11 1798 4 2 1797 4\n865 11 726 9 2 825 27\n866 1 1546 6 1 1543 12\n867 1 1170 8 1 1163 22\n868 1 777 3 2 1030 30\n869 1 920 15 11 1673 6\n870 1 598 2 2 565 25\n871 1 1334 36 11 1273 18\n872 1 581 9 11 1163 18\n873 1 1759 3 1 1758 4\n874 1 1367 27 2 971 18\n875 1 1174 18 1 1168 9\n876 11 2160 7 11 2152 32\n877 11 1566 24 11 1756 0\n878 2 1473 15 2 1887 0\n879 2 1272 7 11 1887 39\n880 1 1179 9 1 1177 0\n881 1 986 9 1 978 27\n882 1 1742 14 1 1738 2\n883 1 1385 9 1 793 9\n884 1 1238 18 1 1228 36\n885 1 1755 6 1 1749 15\n886 11 1820 27 2 1815 18\n887 1 1978 6 11 1986 30\n888 11 892 7 11 889 11\n889 1 401 12 1 780 39\n890 1 597 18 11 594 0\n891 2 3903 1 11 3902 6\n892 1 1206 27 11 1196 9\n893 2 1412 21 2 1404 6\n894 1 1196 26 2 1194 31\n895 2 802 30 11 598 9\n896 1 1803 27 1 1797 0\n897 2 1325 25 11 1314 11\n898 11 1202 9 1 402 15\n899 2 1837 18 11 1969 18\n900 2 4052 1 11 4051 0\n901 11 621 36 2 996 0\n902 1 1508 9 1 1505 9\n903 2 1341 35 1 1485 22\n904 1 1212 9 11 1210 0\n905 2 811 33 11 799 21\n906 1 1998 9 1 1994 6\n907 11 944 3 11 937 33\n908 11 1490 36 11 1479 9\n909 9 3638 1 9 3636 17\n910 1 412 18 1 407 9\n911 11 1162 36 11 1147 36\n912 2 1224 17 11 1217 22\n913 1 1705 6 2 1307 36\n914 1 1838 27 11 1422 39\n915 1 619 38 2 1216 17\n916 11 1230 36 1 1230 27\n917 2 824 27 2 1216 36\n918 1 1833 12 1 1830 6\n919 11 1079 36 1 1485 36\n920 2 827 21 1 818 15\n921 2 1806 12 11 1876 24\n922 1 1030 33 11 1225 0\n923 11 1225 27 2 1442 3\n924 11 1236 7 11 1230 20\n925 11 468 18 11 465 0\n926 1 1863 36 1 1855 9\n927 1 1810 6 1 1808 5\n928 1 1655 9 1 1853 27\n929 11 836 39 11 1445 24\n930 11 520 4 1 773 14\n931 2 1455 21 1 1035 12\n932 1 1243 18 2 614 9\n933 11 1865 9 2 1855 33\n934 1 2427 36 1 2417 18\n935 1 840 27 1 829 18\n936 1 1691 14 1 1687 5\n937 2 1887 36 1 2074 36\n938 11 1624 33 1 1777 3\n939 11 634 19 1 1869 36\n940 1 838 3 2 1038 30\n941 2 1489 33 1 839 21\n942 11 1719 39 11 1708 6\n943 1 1714 21 1 2134 21\n944 1 2107 18 2 1678 18\n945 1 3197 14 1 3191 2\n946 11 1612 27 2 1398 0\n947 1 1707 24 1 1702 12\n948 1 1553 35 1 1540 13\n949 11 1478 3 11 1473 24\n950 1 640 9 11 635 0\n951 1 2177 21 1 2166 33\n952 11 711 33 11 875 24\n953 11 1476 18 11 1263 18\n954 11 2235 2 2 2234 0\n955 2 1485 27 11 562 18\n956 11 3229 21 11 3222 6\n957 11 1313 17 2 1303 22\n958 2 1909 24 2 1900 21\n959 1 1402 18 1 1860 6\n960 1 965 1 1 964 5\n961 2 1083 30 2 1071 24\n962 2 1930 9 2 1924 9\n963 2 1881 14 2 1869 37\n964 1 437 18 2 856 0\n965 2 865 39 11 865 6\n966 1 637 19 11 1244 37\n967 1 1095 24 2 1722 30\n968 2 871 24 1 858 30\n969 11 651 5 1 646 22\n970 1 872 24 11 1078 33\n971 1 1093 18 2 1080 9\n972 1 1910 9 1 1909 10\n973 1 1734 36 11 1730 18\n974 1 1303 36 1 1514 15\n975 11 2931 12 2 2928 0\n976 1 1534 39 1 1086 12\n977 1 1528 6 11 1296 18\n978 1 1942 36 1 1931 30\n979 1 1522 36 11 1300 18\n980 1 879 18 1 876 0\n981 1 1967 10 2 1966 5\n982 1 2186 18 1 2389 36\n983 11 1543 21 2 1743 39\n984 11 990 17 11 985 13\n985 11 1103 33 2 1093 21\n986 2 1878 27 1 1815 24\n987 2 1286 19 2 639 22\n988 11 1325 9 1 877 30\n989 2 1314 27 11 1545 9\n990 9 3962 1 9 3961 8\n991 1 1602 36 2 1595 36\n992 11 1840 3 11 1653 18\n993 2 2135 21 1 2189 39\n994 2 1431 9 1 1659 6\n995 1 739 36 2 1219 15\n996 1 1347 16 1 1342 11\n997 11 2004 36 11 2001 0\n998 1 1327 27 11 903 27\n999 99 4498 10 99 4497 8\n'

def sd(x):
	return sum(map(int, str(x)))

def ans(x):
	print(x)
	return

def hardcode_solver(a):
	if a == 2:
		ans(6)
	if a == 4:
		ans(75)
	if a == 8:
		ans(125)

def powers_of_10(x):
	if 10 ** 18 % x == 0:
		ans(-1)

def single_test(x, drange):
	found = False
	for d in drange:
		t = 10 ** d // x + 1
		ad = sd(t) - sd(t * x) * x
		if ad > 0:
			print(x, d, ad)
			found = True
			break
	if not found:
		print(x, 'Failed')
		return

def test1(x):
	plus = None
	minus = None
	ir = [1, 2, 11]
	ir = [1, 2, 11, 9, 99, 999]
	for d in range(1, 6400, 1):
		for i in ir:
			t = i * 10 ** d // x + 1
			ad = sd(t) - sd(t * x) * x
			if ad > 0:
				if ad < 40:
					plus = (i, d, ad)
			elif -ad < 40:
				minus = (i, d, -ad)
			if plus != None and minus != None:
				print(x, *plus, *minus)
				return True
	return False

def test_f(f):
	for x in range(990, 1001):
		if 10 ** 18 % x == 0:
			continue
		if not f(x):
			print(x, 'Error')
			return

def izracunato(x):
	a = [list(map(int, t.split(' '))) for t in tabela.strip().split('\n')]
	for red in a:
		(idx, i1, d1, ad1, i2, d2, ad2) = red
		if idx == x:
			s1 = str(i1 * 10 ** d1 // x + 1)
			s2 = str(i2 * 10 ** d2 // x + 1)
			ans((s1 + '000000') * ad2 + (s2 + '000000') * ad1)

def precompute():
	test_f(test1)

def task():
	n = int(input())
	hardcode_solver(n)
	powers_of_10(n)
	izracunato(n)
task()


from itertools import *
from timeit import *
from typing import Optional
S = lambda x: sum(map(int, str(x)))

def ceil_s_divisible_a(x: int, a: int) -> Optional[int]:
	z = S(x) % a
	if z:
		z = a - z
		tail = []
		x = list(str(x))
		while x:
			digit = x.pop()
			diff = min(z, 9 - int(digit))
			z -= diff
			tail.append(str(int(digit) + diff))
			if z == 0:
				break
		else:
			return ceil_s_divisible_a(10 ** len(tail), a)
		x = ''.join(x) + ''.join(reversed(tail))
	assert S(x) % a == 0
	x = int(x)
	return x

def smooth25(a):
	a = int(bin(a).rstrip('0'), 2)
	while a % 5 == 0:
		a //= 5
	return a == 1

def solve(a):
	for first in range(1, 60):
		q = str((first * 10 ** 3000 + a - 1) // a)
		for s1 in range(1, 200):
			i = 1
			s2 = int(q[0])
			while i < len(q) and s2 < s1 * a - 10:
				s2 += int(q[i])
				i += 1
			for len1 in range(i, min(i + 10, len(q))):
				small = int(q[:len1])
				for z in range(4):
					small = ceil_s_divisible_a(small, a)
					if S(small * a) * a == S(small):
						return small
					small += 1
	return None

def powform(x: int) -> str:
	s = str(x)
	try:
		i = s.find('00000')
		return f'{s[:i]} * 10 ** {len(s) - i} + {int(s[i:])}'
	except IndexError:
		return str(x)
if 0:
	for a in [999, 909, 813, 777, 957, 921, 855, 933, 831, 942, 891, 846, 807, 783, 888][1::3]:

		def work():
			nonlocal x
			x = solve(a)
		t = timeit(work, number=1)
		if t > 0.5 or x == None:
			if x != None:
				print(a, t, '>>', powform(a * x))
			else:
				print(a, t, '>> ?????')
special = '\n660 0.5026652759997887 >> 3 * 10 ** 2640 + 35340\n803 0.5102322779994211 >> 3 * 10 ** 2678 + 1614\n912 0.5136937369998122 >> 3 * 10 ** 1825 + 240\n918 0.5238579140004731 >> 3 * 10 ** 1813 + 1104\n582 0.5302371079997101 >> 2 * 10 ** 2328 + 17116\n612 0.5363936909998301 >> 2 * 10 ** 2413 + 10348\n495 0.5372351949999938 >> 3 * 10 ** 2969 + 16305\n927 0.5433051690006323 >> 3 * 10 ** 2195 + 21003\n636 0.5471086210000067 >> 3 * 10 ** 1379 + 20004\n531 0.5475810970001476 >> 2 * 10 ** 2140 + 439\n64 0.5633312410000144 >> ?????\n200 0.5639609099998779 >> ?????\n100 0.565854023000611 >> ?????\n125 0.5663040710005589 >> ?????\n160 0.5668467480008985 >> ?????\n800 0.5676178080002501 >> ?????\n128 0.5676772269998764 >> ?????\n80 0.5682811480000964 >> ?????\n256 0.5685735130000467 >> ?????\n250 0.5691464900000938 >> ?????\n512 0.569266141999833 >> ?????\n32 0.5692826909998985 >> ?????\n50 0.5692834940000466 >> ?????\n25 0.5696684799995637 >> ?????\n400 0.5703751219998594 >> ?????\n20 0.5706145570002263 >> ?????\n500 0.5742691679997733 >> ?????\n640 0.5749700739997934 >> ?????\n40 0.5768258159996549 >> ?????\n625 0.5775357299999087 >> ?????\n16 0.5789494729997386 >> ?????\n833 0.5855263899993588 >> 3 * 10 ** 2286 + 1404\n792 0.5996652009998797 >> 3 * 10 ** 1903 + 16008\n320 0.6031684260005932 >> ?????\n10 0.6464516910000384 >> ?????\n546 0.6579458010000963 >> 3 * 10 ** 2184 + 2454\n5 0.6617960960002165 >> ?????\n907 0.664109037000344 >> 3 * 10 ** 2538 + 2223\n923 0.6807242180002504 >> 2 * 10 ** 2476 + 4141\n723 0.6976773409996895 >> 3 * 10 ** 2892 + 1185\n825 0.701172955000402 >> 4 * 10 ** 2476 + 123350\n906 0.7062042559991824 >> 4 * 10 ** 1998 + 104\n905 0.7086789289996887 >> 2 * 10 ** 2412 + 1540\n911 0.711649564000254 >> 2 * 10 ** 2612 + 2044\n934 0.7246100349993867 >> 2 * 10 ** 2570 + 51112\n765 0.7552886830007992 >> 3 * 10 ** 2939 + 1725\n981 0.7653923980005857 >> 4 * 10 ** 1965 + 1022\n333 0.7884190810000291 >> 3 * 10 ** 2994 + 62934\n663 0.8130600629992841 >> 3 * 10 ** 2546 + 11634\n444 0.8443964660000347 >> 3 * 10 ** 1999 + 13956\n720 0.8445076829993923 >> 2 * 10 ** 2779 + 159280\n867 0.9858260920000248 >> 5 * 10 ** 1739 + 121\n914 1.0558696210000562 >> 3 * 10 ** 1831 + 222\n606 1.1190159360003236 >> 5 * 10 ** 2910 + 1318\n948 1.1529914639995695 >> 6 * 10 ** 2466 + 1020\n1000 1.2245053040005587 >> ?????\n741 1.2366985769995154 >> 5 * 10 ** 2669 + 175\n819 1.292531102999419 >> 8 * 10 ** 2949 + 31312\n867 1.293641017000482 >> 5 * 10 ** 1739 + 121\n961 1.431375496000328 >> 4 * 10 ** 1935 + 1112\n913 2.0632996949998414 >> 5 * 10 ** 2323 + 16\n861 2.1641551399998207 >> 11 * 10 ** 1847 + 1114\n992 2.2718322470000203 >> 11 * 10 ** 2207 + 1504\n936 2.3109037909998733 >> 11 * 10 ** 2108 + 3112\n996 2.3603119750005135 >> 11 * 10 ** 1979 + 4300\n951 2.380345242999283 >> 11 * 10 ** 1820 + 412\n969 2.471255187000679 >> 11 * 10 ** 1942 + 241\n828 2.504634874999283 >> 11 * 10 ** 1595 + 11212\n693 2.5246166990000347 >> 13 * 10 ** 2494 + 423014\n840 2.5490226490001078 >> 11 * 10 ** 1681 + 13120\n983 2.618962229999852 >> 11 * 10 ** 1968 + 5011\n963 2.641272683999887 >> 11 * 10 ** 2026 + 133\n972 2.741184581000198 >> 12 * 10 ** 2130 + 312\n555 2.787974407000547 >> 11 * 10 ** 2497 + 444445\n873 2.8377116049996403 >> 11 * 10 ** 1774 + 133\n903 2.898315477000324 >> 13 * 10 ** 1726 + 32\n804 2.9635119349995875 >> 12 * 10 ** 1659 + 1500\n864 3.032601443999738 >> 13 * 10 ** 2747 + 34016\n759 3.0681308859993806 >> 13 * 10 ** 2504 + 311441\n871 3.4960390779997397 >> 13 * 10 ** 2995 + 2405\n902 4.413119433999782 >> 12 * 10 ** 1506 + 1110\n997 4.446912733999852 >> 11 * 10 ** 1999 + 7\n993 5.025415283999791 >> 23 * 10 ** 2130 + 31\n837 5.286188959000356 >> 25 * 10 ** 2722 + 11063\n786 5.390603378999913 >> 21 * 10 ** 1572 + 4002\n801 5.4837765329994 >> 22 * 10 ** 1645 + 212\n882 6.045185064999714 >> 22 * 10 ** 1822 + 1130\n990 6.413724044000446 >> 39 * 10 ** 2970 + 302010\n666 6.967028857000514 >> 33 * 10 ** 2997 + 32934\n941 6.982767053000316 >> 21 * 10 ** 1885 + 312\n924 7.134165846000542 >> 34 * 10 ** 2772 + 1110152\n858 8.089877333000004 >> 41 * 10 ** 2573 + 12201142\n939 8.241953895999359 >> 33 * 10 ** 1879 + 20001\n813 3.1825667919993066 >> 3 * 10 ** 4065 + 7314\n921 1.9310127280004963 >> 1 * 10 ** 3762 + 18008\n831 1.683305384999585 >> 1 * 10 ** 3702 + 1646\n846 1.4100486610004737 >> 1 * 10 ** 3419 + 44234\n888 6.891388972000641 >> 3 * 10 ** 3998 + 27672\n909 11.340291348999926 >> 7 * 10 ** 4673 + 17201\n957 1.3982879649993265 >> 1 * 10 ** 4347 + 28403\n933 0.9980270719997861 >> 1 * 10 ** 3746 + 233234\n891 0.8806926099996417 >> 1 * 10 ** 3957 + 1079\n783 0.6478317080000124 >> 1 * 10 ** 3162 + 22814\n999 102.2252583720001 >> 89 * 10 ** 4760 + 20071\n777 37.847382832999756 >> 24 * 10 ** 4661 + 474123\n855 0.934857464999368 >> 1 * 10 ** 3420 + 21545\n942 1.0410122209996189 >> 1 * 10 ** 4198 + 310058\n807 0.7532789589995446 >> 1 * 10 ** 3234 + 1307123\n'
a = int(input())
for line in special.splitlines():
	if line:
		(expr, out) = line.split('>>')
		expr = expr.split()[0]
		if int(expr) == a:
			print(-1 if out.strip() == '?????' else eval(out) // a)
			break
else:
	print(solve(a))