题目描述
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