P17263 [HackerEarth] Unfortunately Crookshanks(Laurent's cat) has eaten the problem statement. Are you good enough to solve it without the statement?
普及-
题目描述

Unfortunately Crookshanks(Laurent's cat) has eaten the problem statement. Are you good enough to solve it without the statement?

Input Format:

The first line contains T denoting the number of test cases. The next T lines describe test cases and contain two integers each: X and Y.

Output Format:

For each test case print one answer for that test case.

Constraints:

T ≤ 1000

1 ≤ X,Y ≤ 10^9

SAMPLE INPUT
6
37 1
26 1
42 1
50 2
371592 2
136520 1532

SAMPLE OUTPUT
58
40
20
29
118
16

输入格式

见题面

输出格式

见题面

样例输入
1000 309 783 370 339 599 410 410 880 680 606 945 220 244 732 832 474 214 684 659 100 707 487 670 17 918 555 387 686 621 983 979 355 740 810 259 537 857 126 113 42 304 458 143 576 824 567 944 162 413 154 417 475 1000 939 930 85 941 84 437 21 691 654 334 896 394 504 948 462 608 584 71 437 444 774 307 1 679 135 773 289 152 383 163 365 135 321 833 958 652 27 57 901 409 964 866 856 566 721 230 994 188 609 333 170 749 276 478 446 538 946 70 56 972 979 66 81 407 186 18 757 180 734 159 990 735 571 760 164 673 270 623 701 991 863 713 89 402 923 590 16 160 946 861 967 195 726 884 760 569 301 415 201 149 271 880 152 508 107 382 212 899 734 937 702 710 748 349 385 60 628 36 799 498 39 945 742 637 776 739 194 285 562 319 36 830 125 362 386 161 626 494 560 451 313 34 943 900 248 319 36 650 822 128 363 679 208 970 333 810 362 126 503 458 665 371 484 136 697 622 94 621 114 182 648 393 664 900 374 983 338 329 384 213 433 555 92 8 549 961 555 729 676 820 231 785 979 33 434 722 794 669 394 833 50 888 195 430 281 134 684 87 282 601 350 629 6 755 857 997 982 676 890 682 676 487 945 217 711 234 86 405 904 93 247 252 707 875 482 666 303 895 417 229 816 569 110 641 67 98 268 773 155 92 552 190 124 366 982 691 518 238 424 921 195 160 428 655 203 518 509 725 95 521 901 641 700 96 560 194 434 326 891 745 53 433 510 733 539 473 358 814 807 461 376 701 708 45 51 282 885 83 988 757 155 123 607 282 479 790 707 231 603 625 311 200 828 172 667 718 266 1000 321 659 674 56 589 769 762 859 690 628 70 729 14 125 154 117 736 577 345 75 889 417 429 522 432 387 670 859 529 474 160 251 119 897 927 973 944 118 133 20 882 13 368 352 645 267 117 895 200 197 704 127 88 119 96 265 485 698 165 168 230 400 533 226 48 914 767 406 25 84 46 535 731 15 786 664 551 615 74 801 887 535 198 354 65 690 4 158 687 828 672 105 827 561 337 829 507 803 833 841 688 986 780 988 357 935 484 649 677 827 572 251 333 830 818 292 459 946 962 240 223 241 992 744 736 508 69 492 577 494 941 184 869 489 935 379 159 32 791 91 271 196 800 894 778 387 589 949 400 806 337 433 35 762 756 355 549 202 16 143 594 3 540 458 455 496 504 740 75 832 746 391 101 253 88 816 709 270 350 397 254 527 865 497 435 295 388 548 498 323 626 727 190 513 741 902 360 592 254 423 23 727 989 627 62 419 299 890 799 230 941 364 719 860 723 558 73 63 904 50 534 518 572 722 540 553 96 902 310 457 585 148 340 390 49 80 212 617 225 949 352 803 50 851 673 78 589 681 171 819 153 965 386 899 437 593 462 35 294 969 154 114 554 659 634 37 797 399 45 165 267 919 728 798 958 344 668 988 242 282 331 778 454 541 126 204 909 477 386 470 86 719 747 667 304 884 945 699 833 134 938 351 792 826 478 967 352 797 730 679 743 833 47 117 288 650 986 382 485 588 417 18 848 488 531 446 267 296 568 536 693 327 290 88 904 284 396 630 856 8 465 622 934 799 808 844 517 748 702 148 404 712 115 712 588 604 688 8 739 317 432 454 778 232 999 72 835 471 360 289 463 851 763 442 726 242 813 830 215 499 681 132 658 280 191 840 51 651 259 20 633 925 969 202 367 443 103 942 682 562 43 715 316 845 94 195 192 524 504 283 966 559 284 966 416 324 815 417 68 510 540 48 4 742 67 735 349 191 267 51 677 164 165 914 791 861 867 704 514 299 31 308 552 200 623 515 588 539 89 644 400 451 523 564 245 482 54 371 571 763 19 902 458 127 926 927 825 61 217 434 199 817 859 433 855 415 138 763 513 583 622 784 430 603 456 897 499 327 905 686 633 393 679 416 931 538 317 761 673 308 298 720 748 988 540 817 98 882 797 597 740 231 278 702 118 678 458 199 862 775 62 609 447 840 503 561 743 525 163 16 399 994 452 707 323 998 234 605 386 434 320 218 359 235 808 702 464 221 674 861 334 625 923 740 838 72 722 704 359 680 384 702 108 999 208 82 243 118 716 797 390 176 194 633 337 771 910 991 501 598 657 291 356 613 449 510 413 281 426 293 329 355 76 960 887 763 662 462 484 100 332 328 6 395 684 859 914 263 486 586 924 851 460 107 111 803 520 936 372 883 861 321 335 54 999 681 384 526 710 47 31 416 464 750 227 842 710 631 443 744 129 846 837 299 566 138 647 739 279 361 860 742 171 836 481 802 121 559 215 992 376 148 803 258 481 152 812 751 568 78 171 196 111 147 145 301 502 803 181 285 408 386 428 435 406 925 94 565 849 58 21 625 659 118 944 994 383 398 729 409 657 392 915 212 768 435 767 339 931 124 904 913 473 419 644 512 301 101 182 312 800 995 569 58 992 324 7 416 89 615 34 559 659 908 393 472 140 468 671 348 22 85 416 671 267 195 653 318 839 588 249 452 30 386 316 201 247 823 655 388 969 892 304 371 620 523 439 945 690 998 314 152 415 751 510 943 38 2 742 486 997 408 600 247 843 782 564 7 448 350 400 350 221 132 458 660 405 764 957 293 523 74 951 495 286 50 384 241 281 465 95 558 215 580 122 547 830 904 788 605 755 194 602 71 678 760 792 434 886 400 697 502 519 688 830 233 178 717 489 630 526 960 969 144 533 606 159 814 809 399 801 193 111 650 918 229 580 216 27 925 902 70 789 555 942 951 383 158 76 721 774 780 971 358 651 578 734 679 151 570 674 692 653 893 989 839 347 201 702 27 106 157 247 943 840 923 464 343 131 358 333 501 401 788 705 452 61 606 844 62 363 134 650 311 455 744 829 929 762 524 22 865 269 307 775 490 547 976 124 458 337 177 587 82 969 223 184 401 807 891 397 252 178 657 529 583 135 681 23 679 586 12 362 843 389 813 159 201 477 225 59 365 922 743 750 928 303 124 16 382 930 472 250 568 301 893 110 452 158 770 483 82 235 75 867 361 913 116 95 993 918 926 357 827 789 745 656 134 993 122 568 803 829 831 531 451 819 425 491 600 890 970 40 617 117 248 737 475 753 912 791 692 951 983 650 346 722 141 855 988 601 627 929 7 57 63 615 852 828 789 270 328 478 761 664 93 713 219 396 303 342 762 182 498 670 604 58 754 161 469 949 851 551 334 940 435 636 800 224 996 112 633 496 815 407 487 353 869 486 963 19 728 7 328 334 146 837 685 644 84 651 783 592 835 737 362 399 878 992 754 724 35 712 949 241 754 495 948 908 858 796 378 272 868 756 372 893 709 148 226 586 152 423 541 832 611 329 185 242 505 93 77 620 496 595 41 353 556 85 656 177 508 284 263 361 971 253 213 756 411 322 787 578 309 461 981 87 308 87 330 255 787 129 129 320 212 762 118 791 635 354 315 719 554 85 586 671 110 35 34 371 739 63 320 845 52 854 185 500 517 25 93 652 901 414 63 863 166 243 706 405 55 893 70 880 13 423 283 578 933 77 749 865 965 731 50 771 436 889 992 806 495 657 26 314 878 620 109 515 535 872 886 673 177 302 999 74 52 939 106 601 15 964 405 192 826 351 671 267 630 110 114 558 650 407 194 578 511 745 140 730 726 257 323 900 881 157 919 718 464 568 983 190 549 79 394 350 298 186 192 598 745 102 823 404 741 473 523 121 552 535 117 869 132 356 87 350 750 651 583 428 400 254 643 367 38 110 92 420 804 572 886 925 502 80 118 384 808 57 926 570 704 429 862 892 441 483 28 286 17 991 341 107 637 797 28 901 779 905 3 266 641 582 952 894 37 596 929 209 109 998 747 515 216 628 129 23 900 686 320 174 289 913 499 277 70 534 619 448 676 729 751 807 704 823 485 697 213 810 64 449 433 265 683 334 79 411 892 30 725 955 77 340 487 426 719 912 604 792 705 144 168 981 40 901 858 399 927 296 943 163 241 550 959 321 476 385 6 458 49 176 54 156 890 825 339 681 619 277 631 732 756 364 951 821 950 922 351 166 13 994 826 558 437 793 421 230 96 957 388 841 950 590 220 248 47 557 268 54 350 60 358 705 270 141 299 410 9 175 286 541 774 486 711 772 796 937 563 824 901 225 986 505 645 920 882 384 123 87 882 538 103 556 850 615 749 691 473 291 690 460 223 955 84 125 5 108 542 664 90 448 349 87 336 177 397 814 134 539 88 169 494 836 432 719 306 6 379 950 132 688 71 465 980 185 982 959 973 934 900 76 682 709 807 949 213 266 518 8 256 441 189 689 504 916 576 259 207 959 271 886 953 962 409 149 826 558 404 579 135 786 324 791 418 39 850 476 97 491 720 901 905 418 730 760 495 587 607 945 976 857 41 811 643 984 945 818 732 738 558 987 962 833 992 111 810 415 24 292 901 916 547 982 337 823 303 654 564 336 501 897 614 556 960 20 136 618 29 262
样例输出
89 145 42 42 1 4 20 89 37 16 37 58 4 37 89 89 16 42 58 20 37 42 89 42 4 20 1 37 20 58 16 20 4 145 1 89 58 58 20 20 58 89 20 1 37 58 1 42 1 1 1 20 16 1 145 1 4 42 16 89 145 89 58 42 1 1 145 4 16 4 58 89 89 89 37 42 37 37 42 42 1 1 58 16 20 58 42 37 1 1 42 1 42 1 37 89 42 20 42 1 42 42 4 1 16 89 42 58 4 1 20 58 58 89 42 1 42 16 89 42 16 1 4 4 20 20 1 1 16 37 42 20 17 89 20 58 16 1 58 20 145 89 4 20 145 20 58 58 16 4 16 37 1 89 16 37 1 145 1 37 37 16 37 89 145 1 37 145 89 89 145 42 58 4 37 145 20 89 89 1 4 42 58 20 20 1 20 145 37 4 58 58 42 145 145 20 16 145 37 20 42 58 16 1 16 16 1 145 4 42 89 89 4 89 4 58 145 1 37 16 89 37 4 4 4 42 145 4 40 89 89 16 20 145 37 42 20 42 4 1 4 16 58 42 1 145 42 42 4 42 16 58 42 1 1 1 58 16 16 89 1 37 20 89 42 4 16 89 1 37 89 1 4 37 89 1 89 4 16 20 20 89 58 37 58 4 58 16 42 58 1 20 1 42 89 42 16 16 20 4 42 37 42 58 1 89 58 42 16 4 42 20 1 37 145 42 4 20 20 16 16 42 4 16 58 4 37 58 58 20 145 20 16 145 145 4 42 58 4 145 20 1 145 37 20 42 20 20 1 16 1 4 37 16 89 4 1 16 4 1 37 20 4 4 37 20 20 145 16 89 16 4 16 37 4 145 20 1 16 16 4 42 145 89 20 37 16 58 42 89 4 4 145 4 4 37 29 42 145 58 58 58 37 4 16 20 16 42 16 145 1 4 20 58 37 1 89 37 42 37 89 4 42 20 1 16 1 89 145 20 20 37 16 4 1 58 37 145 20 16 4 58 89 89 89 37 58 145 145 20 4 4 42 1 37 145 37 4 42 20 58 37 145 4 42 1 37 4 1 4 16 1 145 16 58 20 1 4 58 145 1 58 58 1 58 1 4 4 4 1 20 16 42 16 4 58 89 89 145 145 42 42 16 58 37 20 89 42 145 1 58 42 1 1 58 4 16 145 4 145 20 37 145 1 42 89 1 145 58 1 4 37 89 58 145 1 1 145 42 42 42 1 20 16 89 145 145 58 4 20 4 20 145 20 42 16 58 1 58 145 42 37 1 42 16 20 37 58 20 42 1 58 58 42 145 89 42 42 4 1 20 89 20 37 37 1 42 37 4 20 16 89 145 58 1 58 145 145 37 58 16 4 58 20 89 37 145 37 89 20 145 1 42 20 4 58 1 58 145 16 37 20 42 58 20 4 42 16 20 145 4 89 4 1 37 4 20 58 16 16 37 4 89 58 37 37 4 16 1 89 42 42 1 42 145 37 20 42 37 89 37 16 4 145 89 4 1 89 16 42 89 145 4 37 37 42 1 16 4 20 37 42 16 145 20 145 42 16 4 20 145 1 1 42 42 1 4 42 37 145 37 89 1 58 4 4 4 1 42 1 89 16 145 37 42 1 89 58 58 20 89 89 89 1 16 20 58 4 58 20 16 89 89 1 37 16 20 145 89 58 16 89 16 58 1 1 58 145 16 20 89 20 1 20 1 1 20 1 16 16 4 42 37 89 4 145 145 1 20 58 1 145 16 37 16 58 1 1 20 16 42 16 1 58 89 20 89 1 1 89 4 42 4 58 16 42 145 16 42 1 20 42 16 37 89 37 37 145 89 1 37 89 20 145 42 4 89 16 1 89 1 37 58 42 89 1 58 42 145 16 58 37 16 37 16 20 42 20 20 42 37 37 16 89 58 58 89 16 4 1 42 16 1 1 89 20 89 58 42 16 1 4 16 1 89 1 58 16 1 58 37 89 42 42 20 16 4 1 1 4 42 20 1 89 4 42 37 145 89 145 58 89 145 42 145 1 16 145 89 4 58 16 58 37 89 1 58 20 89 16 20 42 42 89 58 58 89 58 37 145 37 58 16 16 1 1 89 37 89 89 42 1 37 4 16 4 16 58 89 89 42 20 145 1 16 58 4 4 29 1 145 4 145 16 1 37 37 16 20 145 4 42 16 4 145 37 42 1 58 1 4 4 145 20 1 58 37 37 20 58 16 16 4 42 4 4 37 20 42 37 1 58 4 89 37 20 37 4 16 4