input

50

1 7
4 7
1 5

94 36
16 12
94 12

428685712 23000073
596516650 23000073
428685712 189641422

478160381 19632786
783368691 19632786
478160381 102520060

304089172 540383427
365180541 222688882
365180541 540383427

35005212 521595369
35005212 162170322
14660871 521595369

278722862 861021531
336465783 861021531
278722862 233665123

145174068 468703136
145174068 395870394
85295453 395870394

106596977 635723059
106596977 490175108
315634023 490175108

28561071 89018457
59961394 89018457
59961394 54145816

131176230 607790171
131176230 653377374
72427041 607790171

517747628 459797248
608413785 756898538
608413785 459797248

80978201 30146042
149798316 30146042
80978201 38664371

412776092 324972892
260655588 324972892
260655588 424268981

18258955 42999171
137806863 6499768
137806863 42999171

402370166 54496881
511702306 84420926
402370166 84420926

233090509 41356669
572660337 159126506
233090509 159126506

100661314 433925858
34341670 433925858
100661314 84353895

119259648 865691
119259648 1100546
939819583 1100546

610515435 585990365
153313173 174323385
153313173 585990365

477171088 356426809
467946188 107813133
477171088 107813133

491705403 499715481
780695789 709393585
491705403 709393585

752392755 474612400
549214422 314870260
752392755 314870260

120848385 296223274
120848385 843993369
411549677 296223274

0 0
1 1
1 0

6 0
6 1
2 1

68 0
49 0
68 2

330573318 56690263
35060062 56690263
330573318 603570493

959997302 485560281
402724286 107649160
402724286 485560281

169274578 158487239
194953866 894429690
169274578 894429690

177724267 8639737
221558441 270744730
221558441 8639737

92977305 690387
92977305 7905772
114738098 7905772

21583857 498777856
21583857 791698928
610120710 498777856

72075088 522532257
255179498 522532257
255179498 524872354

82950912 192099256
82950912 703964684
269455307 192099256

112805732 40332872
160051529 31061285
112805732 31061285

199620254 515530020
199620254 26773308
378409504 515530020

409959709 4297113
409959709 77486716
143347213 77486716

113403633 289700724
113403633 168002245
200747797 289700724

150122847 2269747
90155839 439493452
90155839 2269747

231192380 622597489
111537764 338888228
231192380 338888228

147469842 438792351
141527089 438792351
141527089 269441500

13628669 116087765
142757035 116087765
142757035 39237149

8936988 387346491
6321447 982275857
8936988 982275857

350322228 841148366
350322228 77985204
209098719 77985204

473165004 186452552
473165004 39636468
771151433 186452552

187594922 128448265
476153276 213975408
187594922 213975408

653468859 130794396
653468859 53539693
585567170 53539693

605908236 350573794
76065818 203599252
76065818 350573794

1 1
0 1
0 0