TEST DATA FOR `divide'

Input for test 1

2 8
1 2
6 7
3 6

Output for test 1

3

Input for test 2

1 10000
5 9
769 774

Output for test 2

556

Input for test 3

2 100
3 5
7 12
11 17

Output for test 3

-1

Input for test 4

1 200
10 11
135 153

Output for test 4

-1

Input for test 5

4 202
10 12
21 27
32 39
103 121
163 180

Output for test 5

10

Input for test 6

10 10000
100 110
6779 6815
8786 8868
2118 2130
3600 3668
2376 2409
6834 6849
5489 5610
249 314
2206 2269
8043 8205

Output for test 6

46

Input for test 7

40 50000
100 120
22449 22625
37433 37570
23649 23790
4152 4172
4627 4644
36085 36269
9602 9626
16806 16996
6274 6424
19366 19492
23226 23346
30586 30668
27181 27405
40173 40331
38226 38414
21948 22176
42313 42467
6700 6702
19913 19946
11575 11630
9222 9228
11879 12053
11076 11091
31278 31478
17392 17478
38825 38943
14344 14347
34349 34484
36437 36469
26524 26671
30952 31036
21149 21150
14822 15009
18725 18868
23596 23724
47429 47572
7339 7491
34901 34943
19162 19306
32319 32536

Output for test 7

216

Input for test 8

250 200000
5 25
5350 5364
10540 10542
176825 176827
154827 154832
78058 78059
47095 47097
190704 190723
102547 102569
58628 58633
82618 82642
3697 3707
152900 152909
45101 45103
93732 93749
198267 198278
137759 137760
157497 157510
12093 12114
18698 18714
14292 14305
89606 89607
45291 45303
187397 187405
78733 78736
130880 130882
189966 189988
4678 4699
53179 53193
76491 76509
92715 92717
175741 175754
136980 136996
45815 45821
145146 145151
33947 33965
87277 87300
116742 116757
162437 162457
24958 24965
193901 193924
48714 48728
185924 185943
103570 103594
49563 49588
15344 15346
76568 76586
54695 54711
79079 79104
197311 197334
20499 20524
96616 96630
90325 90347
95879 95880
55738 55739
50597 50602
34421 34427
118487 118512
46509 46518
67020 67021
123450 123458
162759 162762
181345 181369
188094 188110
43400 43404
176724 176744
52323 52328
95901 95922
20565 20587
10400 10411
83287 83294
45610 45618
153751 153755
89349 89369
120273 120282
16918 16922
107015 107024
139828 139831
169275 169298
128714 128739
172956 172979
172432 172445
174135 174154
158042 158044
64065 64066
193491 193493
163170 163177
179325 179341
165040 165043
53782 53805
61802 61825
98132 98142
190242 190253
67204 67229
167470 167482
191136 191148
28041 28064
136884 136906
114540 114563
84830 84853
26964 26980
110264 110275
117357 117364
104913 104931
80564 80572
152339 152349
174775 174797
12692 12701
969 974
73996 74008
142114 142124
5896 5909
36973 36987
180626 180639
133017 133026
108182 108203
188899 188909
118040 118041
749 750
96098 96107
199193 199215
182325 182347
65840 65858
119982 119991
156974 156997
35511 35520
7644 7647
164273 164292
145187 145211
120443 120467
116266 116282
61520 61539
79613 79636
106321 106346
115465 115490
125785 125808
41743 41752
10166 10183
107959 107973
3978 3990
191621 191646
39719 39743
71005 71017
55433 55435
161575 161596
81139 81148
134354 134357
67181 67182
77512 77517
115168 115180
10536 10547
185790 185811
33301 33307
87677 87680
14614 14631
6142 6162
151242 151263
82822 82826
111406 111418
193852 193875
102465 102472
51495 51500
157219 157236
40527 40545
131596 131605
32724 32740
166086 166090
148084 148097
33994 34003
172669 172685
23531 23552
25417 25429
165690 165696
93641 93662
194789 194813
139254 139266
33393 33414
93957 93980
31272 31291
110230 110253
105643 105647
71441 71454
63568 63592
67337 67344
16878 16888
152948 152960
191027 191044
84175 84190
91521 91539
186855 186856
123809 123834
107031 107037
108483 108487
108356 108381
16008 16030
55211 55213
45065 45071
123497 123516
140194 140207
24979 24984
193620 193641
74411 74429
96413 96423
160764 160775
127596 127616
45366 45375
22675 22686
170667 170672
107599 107621
49409 49432
181066 181069
57656 57660
66520 66533
94873 94890
129413 129418
14664 14677
88102 88106
73079 73097
56170 56190
188412 188435
103666 103667
131105 131112
157343 157347
155403 155424
170863 170872
98141 98150
163349 163360
72785 72810
170194 170213
118369 118388
85889 85898
169046 169049
57062 57087
111081 111082
148835 148850
120529 120551
141276 141296
25476 25482
91032 91040
123151 123176
31202 31211
87405 87421
183990 183997
114798 114799
74736 74742
145678 145681
195920 195929
28210 28224
159067 159086
16469 16479
149813 149836

Output for test 8

4012

Input for test 9

1000 1000000
5 105
633953 634055
818614 818674
176943 176991
985127 985205
100086 100152
697303 697396
622183 622189
631814 631897
228335 228415
41061 41129
425562 425607
849645 849667
385813 385876
978980 979060
295441 295503
708366 708433
369515 369582
398533 398591
751309 751351
163689 163764
469409 469486
540461 540512
388869 388918
993398 993426
634037 634079
307733 307743
304111 304194
848654 848677
824051 824067
61110 61215
912058 912157
877807 877843
660418 660482
338215 338290
489691 489776
246317 246383
899888 899896
237241 237249
778266 778352
878630 878643
105233 105306
172459 172469
896423 896476
926156 926256
112775 112844
333579 333684
624516 624620
781242 781254
552233 552334
456353 456415
851210 851302
947758 947832
717698 717737
447614 447692
600832 600928
710441 710466
552107 552167
998888 998931
593893 593989
340349 340414
370206 370217
570355 570414
740288 740386
525915 525981
215234 215244
27106 27155
308876 308928
823782 823860
421170 421215
774588 774623
773818 773874
186082 186097
36422 36433
452094 452137
501489 501525
40273 40303
251903 251909
113180 113270
502833 502927
974840 974857
875956 876046
357835 357865
458075 458133
812089 812181
195654 195683
58246 58248
93054 93086
737206 737259
273757 273768
163126 163191
776809 776848
202123 202129
848849 848932
565701 565768
902721 902754
514726 514763
519183 519244
169132 169138
209594 209619
388063 388086
822417 822464
94847 94871
709740 709812
229867 229920
158214 158289
447072 447164
300469 300499
628243 628273
232446 232517
164925 164934
447469 447529
310396 310439
857091 857143
273681 273772
562449 562528
832295 832381
482940 483006
283605 283657
816947 816991
400117 400198
804237 804314
570731 570783
177714 177729
509538 509580
141500 141535
325894 325979
386430 386483
549379 549464
70919 71023
57612 57644
460627 460722
113167 113215
955758 955799
697490 697571
40482 40503
530787 530807
610054 610159
70848 70951
573469 573479
50769 50858
316322 316324
864521 864572
894606 894632
174056 174099
818961 818993
261326 261386
230253 230280
879946 880038
710598 710640
80869 80929
37794 37876
864491 864516
838448 838496
623018 623094
378817 378861
459482 459547
975662 975744
395118 395194
712768 712850
601242 601261
17913 17917
562183 562284
99834 99847
73038 73112
394440 394505
271583 271643
804807 804828
256131 256166
219361 219392
962823 962858
208817 208887
798870 798960
939075 939165
402940 402995
743780 743880
931844 931858
889087 889100
457281 457287
302197 302204
642863 642959
213808 213812
550919 550932
189121 189182
562262 562321
69820 69903
355961 356054
233431 233487
202795 202807
892753 892842
494354 494452
107532 107551
147328 147339
779231 779291
946850 946880
258647 258677
886723 886821
710886 710927
417592 417608
108821 108922
271001 271048
435280 435299
119562 119647
339996 339997
953901 953967
301206 301219
321393 321429
151240 151297
794158 794222
246420 246492
519626 519643
344623 344675
895356 895387
434810 434852
287949 288054
980805 980884
867544 867561
749552 749580
695223 695303
127766 127771
927257 927285
462200 462304
682267 682366
918354 918425
659034 659089
917840 917850
936937 937034
737987 738063
614528 614628
6157 6261
622280 622346
855156 855173
440637 440714
514255 514262
772392 772497
234198 234259
894145 894201
207760 207769
298555 298648
573884 573986
928955 929054
617671 617695
320254 320345
849234 849287
19467 19479
77240 77242
976925 977007
755230 755264
24664 24738
497694 497711
961573 961664
493942 493957
191580 191602
747789 747854
766468 766522
285605 285668
342500 342579
262028 262091
36610 36714
833284 833299
902238 902319
686644 686648
481870 481927
726739 726775
182056 182137
953887 953898
519781 519864
429365 429441
253462 253567
160393 160470
186270 186310
64194 64283
826982 827032
25697 25750
887055 887106
683825 683851
774054 774126
508318 508371
243714 243796
92975 92978
323414 323508
361026 361079
625393 625418
572940 572970
506606 506700
24180 24253
964502 964529
59256 59286
126611 126693
277388 277453
95723 95765
409448 409485
378011 378030
494270 494279
175585 175589
416501 416566
265438 265480
178193 178220
705246 705282
122430 122479
128833 128895
697488 697529
295625 295626
812594 812617
915483 915510
784893 784987
597095 597114
791702 791797
317393 317421
413291 413325
751813 751844
669503 669517
527401 527453
123609 123643
311351 311397
426879 426884
170249 170292
741260 741307
815213 815257
969050 969155
902833 902927
689606 689658
128288 128337
225995 226015
296700 296770
783072 783121
189332 189352
109565 109640
866285 866375
470933 471008
48579 48602
806250 806303
538902 538955
985483 985556
933182 933271
943122 943187
422907 422988
750101 750193
617860 617929
142728 142807
475530 475538
697721 697793
553003 553013
362631 362694
549817 549877
865824 865834
53654 53745
201863 201897
349006 349056
741808 741850
339632 339731
43988 44000
15209 15260
356341 356446
379006 379087
512542 512616
436224 436273
48881 48919
289555 289623
214538 214551
867331 867349
161823 161873
524489 524572
158586 158638
132047 132070
659301 659372
187571 187577
556103 556139
492512 492599
812101 812174
600539 600551
932425 932478
264362 264414
641617 641704
684391 684409
607432 607469
380427 380429
774816 774875
800610 800641
640568 640637
411952 411982
725751 725825
452024 452109
279244 279297
997571 997585
388646 388655
640997 641020
794041 794108
242831 242933
706218 706235
746606 746660
345168 345236
409763 409847
59752 59777
493932 494026
178085 178139
143552 143594
912946 912965
964148 964181
22456 22458
547386 547475
645581 645610
622003 622058
33968 34056
659139 659196
302247 302292
18119 18201
4020 4120
262288 262324
203007 203076
170406 170470
845409 845501
513205 513261
966671 966732
621511 621571
557229 557251
565533 565629
523795 523896
823073 823117
965744 965754
226318 226350
118501 118502
808706 808757
551530 551536
695019 695075
138049 138101
82863 82943
573368 573461
604414 604425
841090 841147
273380 273434
527521 527557
904155 904181
705783 705829
377356 377358
695917 695944
615810 615880
167534 167569
358932 358998
172770 172814
118629 118697
977806 977889
454308 454402
290815 290920
425172 425249
277845 277862
782805 782826
815446 815487
853174 853177
747015 747059
767150 767176
618544 618594
605823 605844
874202 874274
425207 425226
801587 801600
37375 37441
468857 468956
812196 812210
400381 400392
799255 799273
29345 29390
764550 764623
865683 865703
637692 637711
475943 475976
622015 622087
494951 494966
340843 340914
59605 59658
793992 794038
861788 861824
229463 229559
962328 962362
873169 873240
85654 85692
621339 621417
227177 227227
497514 497525
465774 465819
904086 904147
163794 163829
315623 315700
613839 613915
205559 205570
317372 317443
220236 220323
712681 712770
164381 164399
407876 407880
478763 478837
949482 949501
973970 974067
394706 394711
514040 514065
483671 483760
694715 694766
963840 963841
864576 864629
534125 534134
811834 811835
287868 287898
290970 291037
303282 303304
158573 158629
863530 863562
81790 81839
486451 486555
609621 609680
603972 604050
364982 365033
63058 63099
409845 409917
121295 121351
628470 628481
909181 909257
599459 599518
323902 323954
716491 716502
532781 532875
769761 769844
28630 28729
283696 283776
884160 884169
294166 294174
277602 277655
59981 60012
774239 774298
258815 258907
449753 449812
309000 309059
894021 894068
548693 548712
52672 52754
546078 546123
818831 818837
929814 929821
292610 292663
922799 922858
660141 660167
515041 515083
134606 134699
683701 683793
224282 224353
699062 699143
581187 581272
751354 751372
633459 633461
507853 507935
331314 331345
809191 809217
372088 372124
315006 315055
806893 806952
213287 213298
627804 627860
52491 52585
781393 781445
688750 688802
621041 621079
363952 363996
482278 482289
46536 46591
333011 333032
633098 633157
98064 98131
83940 84040
677537 677566
454826 454850
74091 74153
433637 433643
696330 696405
912773 912874
447514 447547
362673 362775
797691 797789
977431 977453
741584 741610
432416 432510
411605 411684
442008 442062
616386 616460
489139 489188
684373 684445
80274 80352
556327 556429
668521 668542
1900 2005
127391 127460
364319 364335
971830 971919
191783 191790
759369 759391
126602 126633
498642 498681
236619 236719
979783 979819
615554 615656
604894 604987
201194 201271
208395 208416
805697 805769
99285 99299
870154 870188
911551 911656
290224 290323
81878 81948
281857 281883
816463 816472
908727 908806
189646 189674
940089 940181
600071 600091
823786 823878
816359 816419
998699 998804
466933 466940
611540 611542
345408 345467
113329 113430
690756 690786
679102 679126
551144 551246
982158 982220
23832 23870
460633 460636
109636 109672
818513 818547
856942 857023
397614 397675
584970 584983
121071 121085
156274 156288
668380 668386
358303 358362
155283 155360
486190 486200
994030 994078
703744 703786
493644 493696
892590 892623
619444 619538
628402 628438
812567 812625
12761 12788
744229 744320
144526 144610
900652 900706
549407 549455
263825 263843
364001 364048
492660 492705
166359 166390
664999 665051
175185 175238
110991 111042
928752 928770
322959 322990
288052 288072
570822 570875
656360 656425
240278 240323
123499 123583
184658 184721
931483 931575
484829 484847
357761 357820
985617 985719
60675 60753
191133 191225
934765 934837
488427 488434
976843 976943
12932 13032
9313 9382
594227 594324
937951 938031
342787 342811
593233 593338
263739 263763
876347 876388
444959 445028
649031 649110
481555 481626
436768 436869
887717 887757
985293 985378
861967 862042
54635 54698
309084 309133
600021 600086
963335 963339
914129 914231
596960 596995
41944 42002
11925 11982
261819 261826
29817 29910
957492 957570
269868 269901
341212 341274
778575 778604
236028 236130
728170 728252
174062 174145
452700 452721
64432 64512
147542 147647
507932 507962
37156 37238
773156 773258
730527 730630
523009 523107
662416 662504
559666 559682
870123 870151
302727 302804
130944 131036
52733 52829
480143 480217
652628 652731
19070 19134
211359 211464
394977 395076
581517 581532
482005 482103
232869 232870
201538 201619
645001 645034
589231 589329
985764 985812
651891 651937
399630 399637
136328 136416
983889 983957
500904 500905
411417 411435
399505 399553
65868 65881
207135 207226
622841 622942
226072 226155
758641 758650
445190 445256
392317 392334
183686 183770
768994 769050
785268 785301
190178 190275
236158 236229
162764 162835
213781 213848
761279 761378
554091 554120
579379 579419
392693 392798
544741 544843
623343 623439
258456 258511
687648 687734
277331 277415
770523 770600
743424 743453
25580 25661
5906 5915
590915 590928
882700 882743
589119 589131
178986 178995
532344 532442
142476 142494
205431 205446
97820 97917
67890 67914
311712 311734
33698 33754
767136 767216
470338 470364
394512 394578
827723 827827
108696 108759
194685 194749
852662 852687
609285 609389
569248 569315
264387 264425
396341 396411
62815 62852
396147 396173
866358 866406
198952 198974
346420 346479
228948 229049
561430 561463
759042 759127
295727 295743
211048 211068
133180 133245
624334 624415
189352 189365
517752 517801
121290 121319
847322 847390
347418 347490
57389 57479
508266 508309
355390 355471
835638 835669
112281 112381
863495 863560
377296 377395
460295 460322
859244 859329
487608 487632
697367 697443
55449 55481
30062 30082
745085 745115
780740 780752
790268 790298
454297 454351
827071 827171
751288 751308
851670 851678
871336 871397
639686 639748
794005 794084
392179 392252
180766 180846
382433 382481
799964 800064
80469 80535
259859 259943
648799 648886
975532 975557
935982 936035
581661 581752
559261 559345
697809 697828
386603 386681
125213 125279
517997 518042
112591 112683
645008 645106
492922 493021
677094 677175
844878 844896
576186 576214
725986 726031
84679 84730
720648 720652
190036 190073
34841 34945
795267 795368
578260 578267
782544 782620
554355 554459
932899 932988
97343 97354
531643 531743
277833 277900
803492 803543
61587 61675
43151 43253
516933 517033
682858 682883
631026 631066
947403 947507
601869 601935
826920 826931
5850 5896
148018 148031
38997 39073
586513 586610
329093 329113
731452 731545
17780 17828
247036 247066
803264 803337
875938 876039
983302 983382
360530 360533
765321 765402
305634 305700
970282 970373
887998 888044
906206 906278
978841 978895
531971 532039
428154 428207
909880 909960
730692 730720
395445 395536
172185 172243
532013 532056
528490 528555
420226 420250
997982 998007
544048 544088
855955 855991
45423 45494
290267 290333
27889 27993
489638 489703
173308 173400
654863 654959
219431 219496
594025 594087
357460 357541
693438 693542
476378 476480
632712 632758
235657 235707
387460 387520
968015 968111
60892 60929
382004 382081
453027 453046
374713 374730
148381 148456
140022 140112
230952 230959
220844 220872
568508 568553
540106 540187
290402 290503
467546 467567
577370 577461
109254 109332
948042 948118
638846 638924
709509 709537
231338 231349
328783 328872
68590 68685
920941 920945
736445 736479
426229 426326
819343 819425
19762 19853
559587 559633
866210 866212
449923 450017
42130 42178
637974 637987
713769 713827
78536 78619
958951 959025
698678 698714
721588 721645
134181 134189
722221 722296
222258 222342
875332 875374
770444 770535
199368 199424
664667 664693
952960 952994
167873 167892
988750 988829
970999 971096
87996 87998
850884 850965
454656 454753
516443 516479
1714 1738
711756 711778
572479 572567
877289 877290
655533 655590
638473 638510
345686 345779
253252 253313
559236 559258
527893 527947
611200 611263
932003 932030
868890 868952
984482 984497
33937 34029
928597 928660
712572 712613
195225 195231
962755 962762
807586 807671
883757 883781
307003 307084
615283 615298
751323 751356
163390 163447
137579 137664
739356 739377
130328 130372
45568 45617
194423 194465
511786 511802
190492 190525
575442 575480
794598 794652
926743 926775
986572 986575

Output for test 9

4812

Input for test 10

2 1000000
1 1000
367 2000
2000 2109

Output for test 10

500