15 1000
8192 256 32768 1 32 16384 2048 128 1024 8 16 2 4 64 4096 
1118 95109 41183 30402 39517 82476 75329 37161 34935 53708 47110 60499 56495 28082 45537 60427 38274 49360 27665 53483 17346 97240 35003 31868 41179 91898 90231 63783 52537 55597 47888 51294 50263 507 8316 50468 59812 99269 40023 43246 97579 39745 17802 64547 40126 30109 21615 42806 99659 50568 71381 1025 22607 12635 13794 87390 36315 97008 19469 52622 83935 77134 31320 39116 63691 52441 57582 90655 48250 33291 20988 35134 51402 60511 53348 56769 47546 91061 48668 97793 30819 98601 54633 40382 1445 21776 37355 48236 55333 18334 88172 91071 55757 67013 44292 94055 58386 55722 86695 87188 13256 17569 54705 78579 56564 41212 35233 97478 39015 70132 22084 63772 99248 38315 11316 30073 52695 8508 26827 22598 52734 61622 54446 49178 58823 69648 5958 31622 75732 37698 14743 60366 55323 19878 53315 64822 28877 58944 20537 13438 64816 18656 58701 82694 28684 72424 63950 71092 36876 50422 55567 30795 84492 51423 60466 48627 10485 26710 43241 20705 66212 53683 57736 32411 55659 73335 63503 66830 13728 96322 33232 76251 47419 62781 54577 96072 77320 37235 2142 13698 31970 63857 92258 98833 96219 42363 31126 55864 61868 90192 2390 55672 31052 40272 63538 29103 22712 18753 50185 40998 74958 42461 85084 50355 7748 87900 38021 61909 16524 7176 61662 58333 98920 64926 41939 44163 43414 58679 57502 89116 25595 3533 98453 95886 40250 61670 45018 27794 19833 55773 62443 10518 48153 43046 59409 50633 56482 56672 82715 40384 67976 12561 88560 52726 42257 27799 60488 63809 53511 64240 27972 24933 57574 13030 63907 38063 52383 90420 59872 54935 53438 48447 36945 80390 74245 31983 40135 96006 45525 50440 43617 19824 62646 86479 7674 19924 23800 60612 74515 17471 55347 53276 43861 63110 85034 41215 73432 63547 78387 59522 22808 52255 53902 62947 59619 36091 59873 33960 227 24510 28833 25610 45655 82388 20870 4487 12321 59747 19196 28711 66411 52290 29985 25804 58947 53091 31201 50488 86459 29144 62591 18571 63707 17460 30019 8213 10702 35073 43283 9573 16759 34999 24290 37353 49176 58776 48394 58649 87282 33251 1200 58503 42404 79766 50603 11460 59654 47004 33178 45412 53580 37261 53552 66418 45089 25885 36172 19853 24749 15518 81102 41418 11433 89059 70310 59771 5635 98398 72121 49523 48156 6627 49177 50554 35294 97711 16443 80179 14388 62473 9474 8405 39938 21631 12536 39199 13813 16515 50178 21930 27966 19948 97790 68422 21862 44419 63612 88807 23959 60720 3267 62728 4417 48139 29064 55577 53443 32055 50380 61636 60777 61706 62650 33849 31078 81138 30173 75886 98201 4060 98482 73598 24776 87208 21969 18679 55419 63516 46405 96906 39010 52318 92 47705 79703 17501 27751 51141 63569 60047 52241 7829 13625 97236 4323 33252 23978 51666 53686 41839 8384 57147 59793 98812 31769 79959 37943 28708 45426 34017 86177 83132 34275 55769 55429 10498 53693 3468 17669 52233 44709 50324 27731 48136 42493 91138 94684 52227 44283 42120 8388 8236 48428 65039 84130 61556 10252 64585 98787 28990 90779 60596 16589 29116 91230 92123 19756 57376 64673 48541 98143 18135 55379 27010 13095 39146 87541 90616 50497 62569 58661 43291 37031 63892 61764 46950 57688 17575 55628 6372 88592 56772 96803 45115 23766 38920 89214 98560 62599 22583 7848 76013 12659 1478 9836 48257 62733 64792 40496 80071 63916 3359 25426 34466 64903 36978 18821 61898 62808 42099 49506 32022 58693 58543 11567 25181 39291 57814 38404 3442 26739 57934 84643 8453 50652 14823 54390 50435 63881 17666 48396 26372 96549 51911 49589 30744 62491 44158 61641 82762 73220 41314 51572 49140 31770 60845 35882 40063 48349 29077 53446 39242 26073 95262 89762 25902 89914 12341 9925 25963 59392 64703 37347 63710 71992 9417 83923 20589 70533 51284 45944 4512 46152 44151 8207 45213 94523 59489 10720 71301 41203 12799 59751 1283 22810 88977 53971 93764 38036 51622 93602 27688 98255 89474 51688 47414 13373 4996 53372 45179 85939 92608 75011 86631 30195 56576 62817 73661 14767 93936 40106 60848 39253 39346 42444 80910 7436 72175 49441 60627 87143 43047 53482 97093 15799 41195 41162 4771 46264 91993 32138 5545 70327 33093 13484 43252 42244 32970 50482 46583 6499 34226 34194 5419 30858 24358 18552 98480 8330 45201 55716 36961 49654 57268 35908 51574 27042 60995 43406 39030 44314 26923 52034 18422 52948 53600 47601 61586 60467 52732 54688 29743 91228 44509 26841 35203 88578 18577 1339 41217 54477 61796 55662 38382 23682 63863 55592 56613 71635 39276 59819 62724 75323 60818 59740 90381 37327 14625 82513 43338 77511 83738 55395 82117 24898 63559 40017 60447 62726 88177 35267 92518 12727 60723 14644 68699 21586 48522 40073 19556 25772 63479 54429 90402 9545 25725 51295 46191 82773 22760 20042 41231 24751 29740 23969 60783 50685 48787 82867 20718 14771 85915 47998 97735 33270 48468 31049 94100 6376 13753 98585 26894 55543 7390 60820 54404 26703 56583 37534 54624 94227 99571 2246 8498 60631 64498 64635 2416 30820 12700 60172 83658 63789 28078 44249 62468 20531 64162 59459 10679 13765 54463 58927 81300 58615 48448 56592 22769 53262 56618 53684 96604 37049 83964 79621 29160 17629 27050 14850 72410 58676 47206 59566 68858 64620 27818 86326 47557 54522 99575 9373 37128 40352 84960 61451 46350 69985 97829 54474 95985 24518 42539 32779 54690 71795 43392 57386 87829 37942 30828 12359 19628 55421 54749 67079 20546 77270 44538 24923 52840 47406 19823 46382 59202 62712 61464 14572 9894 62488 64910 54306 58808 33999 77816 59363 48220 91067 30349 61480 4331 470 38969 93564 12523 90580 90246 51357 11655 29923 35158 58668 55341 58280 20343 5208 45120 1353 88677 77064 87507 7225 30933 34044 31106 14225 30141 97966 91750 61946 26973 46470 56734 81342 54666 73738 76279 34944 7552 71107 48356 57496 54553 36168 90534 48589 433 65583 53343 57625 70004 42131 43152 12687 64674 89407 55718 46228 89745 60420 1064 31928 56597 59405 19939 79764 79273 62794 57627 22724 26377 15474 81855 44252 49371 62576 61756 4580 58530 51613 60655 35941 92633 87338 99900 96654 12674 29972 85805 96817 43302 21907 9455 28832 32998 38100 63804 39036 36020 38962 12380