3000 1000000000
0 1 1630704
1 1 1987962
2 2 5589119
3 1 7223970
4 1 32448774
3 1 5188599
6 1 15621780
4 2 17389129
8 2 15014374
7 2 13153103
9 1 36794153
10 2 17730347
7 2 28184637
10 2 48615555
11 1 18325037
2 1 9277594
6 2 49752398
12 2 33656990
16 1 7068153
14 2 66890883
13 1 31734992
21 1 94523370
19 2 7971261
12 1 44624776
1 2 9321322
13 1 34793197
20 1 29458780
24 2 68381956
18 1 67662482
15 1 44657481
21 2 30631604
6 1 21321442
14 1 60849402
27 2 105328738
5 1 44940921
5 1 6343585
36 1 93134482
29 1 148880983
33 1 65473032
23 2 21172739
32 2 10562448
26 2 95046435
40 1 95586916
34 1 262973213
31 2 24844913
27 2 50663567
30 2 105243524
46 1 241992007
35 1 25374725
28 1 125059170
46 1 361784761
36 1 20399159
34 1 47659251
45 1 139669792
40 2 55914032
54 1 144801146
11 2 43474295
57 2 57838338
55 2 87798033
28 1 59546614
39 1 26719666
45 2 61113634
38 2 578695197
40 1 25673826
57 2 129648257
25 2 5774259
35 2 77090606
62 1 173904216
50 2 156035682
66 2 16477247
22 1 68273709
52 2 31853770
36 1 19157644
50 1 179422954
25 1 11088055
67 2 61878670
18 2 60903163
15 2 52518352
73 1 40395149
30 2 44376393
38 1 55129441
39 2 47388245
75 2 8083743
47 1 120155344
72 1 159162857
60 2 68779683
60 2 80450074
44 1 133880089
78 1 100576939
70 1 12684159
80 2 135751074
71 1 172789311
24 2 71435451
89 1 55103186
61 1 122591417
24 2 85216025
73 2 48449207
53 2 124550203
70 2 13652040
31 1 48638126
92 1 70389644
99 1 17095126
76 2 24493387
83 2 10959667
58 1 147034905
90 2 12478878
64 1 23011152
96 1 72205150
77 1 139439918
64 1 75481788
97 1 22609143
72 2 38453049
80 1 173206028
89 1 260067502
67 1 47733123
19 1 5789418
54 1 75985636
87 1 252337822
94 1 200284819
79 2 87306082
81 2 159833921
116 1 17948995
75 2 9515510
108 1 124830741
53 1 180313650
42 1 57218615
107 1 164727143
26 1 22105713
95 1 171972425
128 1 205985806
29 2 106006918
16 2 6260252
79 1 67275550
8 1 36846444
131 1 99568658
32 1 8295246
120 2 50220779
103 1 153326203
82 2 283867395
62 1 158694744
61 1 191261697
123 1 10001828
106 1 29615701
42 2 63150125
131 1 90393888
49 1 49366401
103 1 58092995
145 1 123704451
76 2 55000059
149 1 64652656
92 2 166363874
147 1 237964318
103 2 77232674
105 1 105743489
41 2 12669633
109 2 116377362
9 2 17393284
133 2 100218858
100 2 79159831
52 1 22758550
33 1 29960372
66 1 7620608
23 1 27653303
134 2 25963369
104 1 31351232
126 1 85263135
71 2 100505676
150 1 96564723
41 1 24328965
117 2 141058843
156 2 191254593
90 1 19455569
100 2 82445310
172 1 11046130
164 1 47963896
114 1 157970810
108 2 74933960
166 2 174091337
149 1 48361210
158 1 264235840
158 1 249191644
163 2 40947973
142 2 42130482
102 1 17404630
166 1 65795678
115 1 72623530
182 1 27364874
184 1 37696026
153 2 137099205
126 1 134662491
51 1 208216704
111 2 225677262
138 2 204318874
111 1 74234318
162 1 15822499
144 2 118332793
137 1 154126581
129 2 180078808
169 1 44927382
83 1 7348087
22 2 56181299
196 2 201930549
195 2 8751732
188 1 32802426
165 2 30431879
153 2 122160907
167 1 206981575
202 2 140874384
143 2 27916580
132 2 3177615
78 1 45195714
189 2 202115804
192 1 234878053
20 1 55051556
207 2 176561663
201 2 39547626
160 1 97129900
204 1 216768872
143 2 32833202
110 1 135414591
184 2 85468744
200 2 15860795
187 2 49176142
220 2 33134082
195 2 26024722
55 2 89103822
33 1 278631171
201 2 43285456
221 1 35551008
204 1 135816468
175 2 15436113
188 2 63363416
109 1 103864020
65 1 93758193
55 1 62201766
225 2 28753526
124 2 108426876
162 2 6462480
62 1 82356847
229 1 205027945
235 1 45935402
192 1 166908297
241 1 96123450
82 2 91740950
209 2 32590350
172 1 37029596
192 2 283943633
194 1 153498337
116 1 12668758
120 2 46795260
220 2 65519748
232 2 59615876
154 2 155977396
54 2 208903222
229 1 100813873
251 1 110509412
110 1 25764584
150 2 125916152
228 2 191278042
217 2 82342131
222 2 17580143
234 1 84573428
183 2 35376170
87 2 358219156
187 2 126921297
216 2 147783751
204 1 174143728
133 1 43804256
97 1 90809521
197 1 336324214
235 1 72655897
231 1 74863469
210 2 21232305
164 1 125632305
267 2 103908387
265 1 73928083
217 2 119133980
203 1 29043849
130 1 36873427
272 1 88064554
99 1 12716003
100 2 161748844
232 2 70430064
263 1 30593833
277 2 433513139
157 2 35013094
132 1 27357490
265 2 179575621
272 1 217387994
286 1 46465697
141 1 359709704
167 2 151599832
165 2 16580842
247 1 84427133
249 1 27193295
257 1 194525680
203 1 24051728
122 1 49475671
283 1 68884511
147 1 290037970
298 1 23161325
249 2 19330891
241 2 48536248
106 1 8616923
261 1 34988205
194 1 262644505
214 2 139042772
295 2 30188951
159 1 201027978
210 1 149503264
256 2 176636450
274 2 65561936
245 1 83359246
104 2 21404025
146 1 70413686
246 1 87122097
219 1 39106998
303 1 51071111
209 1 92838834
281 2 30150343
112 1 87020700
290 1 44405764
316 2 33306340
286 2 100658040
273 1 27420838
183 1 99349193
318 2 297697488
245 1 34046789
307 1 162680676
128 2 41077865
184 1 166014010
199 1 58451589
315 1 75171422
314 2 26846704
305 1 270520221
136 2 28807215
230 1 119972106
319 1 53761499
210 2 21237026
155 2 41196309
238 1 35393709
296 2 144860833
223 1 73443740
221 1 76482514
278 2 28036204
302 1 23813434
65 2 121068243
47 2 364008872
77 1 48413252
205 2 48352693
112 2 67810366
324 2 119353767
344 2 59202449
295 2 43614874
175 1 33080166
283 2 374663139
340 1 54886329
332 2 200914925
240 1 141372672
323 2 39035029
303 2 132659181
354 2 211128861
186 1 67013358
211 1 164270341
248 1 170638613
325 1 42147208
274 2 73522222
320 1 29197497
226 1 128784716
340 1 47220502
312 1 111920321
281 1 55957386
146 1 28481393
308 2 392067813
373 1 239854675
173 1 48219677
84 2 108481916
303 1 86125725
196 2 182946828
336 1 46843397
302 1 23485688
297 2 67552612
200 1 19925685
288 1 34394773
380 2 20000429
179 2 79027056
325 1 24334116
360 1 180995828
382 1 54060633
357 2 56914706
371 1 135056503
181 1 176362929
142 1 33686291
347 2 154219740
293 2 19875242
302 1 152751247
287 1 25309858
290 1 133138876
260 2 360576134
328 2 103012860
339 2 57263471
352 1 187172067
271 1 130770163
370 2 64363016
255 1 182262020
91 1 190507271
161 1 30499438
349 1 134714279
345 2 46972916
398 2 100173672
308 1 63575393
174 1 38557742
271 2 150600922
279 2 111399443
268 2 182365439
372 2 12296969
338 1 79384768
366 2 22833389
367 2 129655900
412 2 69461047
387 1 72781268
236 2 29722006
339 2 10756415
276 1 97439868
297 1 20894144
356 2 131701298
375 2 225462963
405 2 136714770
308 1 112745233
304 1 29903121
255 2 138646552
236 2 27238758
390 2 185691744
174 1 98016367
380 1 27985978
301 2 81293831
370 1 197264808
412 2 39811613
320 2 24691440
422 2 140796936
292 1 243177015
223 1 74171185
384 1 130587415
284 2 41510625
368 2 142380481
230 2 80134842
154 1 139410481
234 2 113010604
287 2 9471637
96 2 91660501
384 2 161995022
216 2 151927855
136 1 25241403
243 1 131010053
409 2 136749255
211 1 128629913
390 2 156539434
214 2 73509596
413 2 91828738
226 2 187990830
387 1 66249855
429 1 57363872
105 2 116708081
134 1 21612199
323 2 86230763
410 1 80627383
150 2 152722389
293 1 83198939
240 2 67309039
404 2 129056878
369 1 272280533
436 2 85089640
321 1 171609142
305 2 59625894
408 2 209603496
163 2 18604985
394 1 60582986
338 1 182987371
252 1 69253471
476 1 20733995
277 2 157401700
309 1 70130917
450 1 206095505
409 1 142103587
159 2 178958913
239 2 340944826
458 2 130581109
419 2 202324489
334 1 28564889
418 1 35552378
244 2 199947783
147 2 22008101
462 1 39784139
238 1 191702857
289 1 182830761
435 2 149534816
346 2 55842265
423 1 53529591
489 2 46114766
403 1 210110518
413 1 149524820
137 1 291040602
275 1 79915502
393 2 40133716
472 2 143003630
497 2 120159961
425 1 76283714
342 1 216523272
388 1 130918798
455 1 121518150
460 2 79272644
363 1 184799522
267 2 174939944
372 1 30767388
371 1 72456512
368 2 54352146
354 1 62168541
419 2 167372963
407 2 116014902
416 1 67074729
360 2 109687329
465 2 181083936
190 1 244189993
330 2 91372697
478 1 183100097
369 1 50682312
375 1 146600263
450 2 181762033
417 2 393090511
516 1 142062266
381 1 78684968
333 2 73207618
469 2 306640591
480 1 144430457
440 2 33196512
418 2 77743389
512 1 457255588
296 2 226608084
160 2 118061609
222 2 70652026
288 1 247974380
284 1 66496025
502 1 297004946
474 1 86093055
219 2 29065555
456 2 156366571
252 2 95204089
316 1 79602184
75 2 132638110
464 1 102392497
269 1 65389612
386 2 222501563
496 1 100571461
231 1 51181890
334 2 106734804
397 1 28333896
407 1 98640538
343 2 132779292
535 2 97060082
383 2 20333463
421 1 51319713
385 2 161865349
224 2 227519017
559 2 100920448
541 1 154554985
483 2 366683677
517 1 53861576
263 1 49406532
517 1 60979290
548 1 516727994
524 2 61893665
496 2 129817838
499 2 66640126
344 2 68428430
558 2 124288623
355 1 87575780
576 2 63920528
560 2 52427186
526 2 128474699
578 2 44937297
544 1 242598135
490 1 96519993
408 2 163070276
442 2 261013500
298 2 117074988
579 1 95884440
434 1 44881224
350 1 84866255
468 2 153255019
438 1 102229236
313 1 188726527
578 2 62596468
542 1 122973586
546 1 235694903
355 1 111241824
319 1 109192887
531 1 83186226
182 1 59177672
58 2 55989326
568 1 42027630
395 2 18569467
369 2 91280403
470 1 203962075
427 1 409543668
420 2 71288186
398 2 560133440
224 2 207256577
515 1 149643571
491 2 172092241
395 1 452651762
464 1 68082395
515 1 142750791
414 2 264589837
107 1 29037302
480 1 46041193
332 2 77366487
550 2 32120862
411 2 37861170
454 2 163407796
588 2 91305130
597 2 152306681
506 2 123805785
157 2 40560378
479 2 100065381
440 2 24264061
511 1 91136667
250 1 142226347
439 1 36466246
472 2 217126248
625 2 28338139
539 2 141645675
605 1 75113861
461 2 84484989
177 2 71494336
155 2 56912442
262 1 92242329
582 2 78066527
130 2 114223847
593 2 113420649
497 1 107771767
473 2 220867406
628 2 69247786
607 2 154252973
389 2 207586281
314 2 42600798
474 1 75647256
520 2 92222651
49 1 27409608
498 1 86849233
611 2 128805783
490 1 135394843
449 2 20752814
381 1 60667300
576 1 238670838
353 1 198243981
444 2 93054629
363 2 292303309
554 2 96620234
555 1 48357701
607 1 215980143
439 2 23808640
521 2 398145300
498 1 33875799
590 1 145176690
506 2 103667801
536 2 58699143
550 1 29635361
383 2 24371164
385 2 74456941
666 1 410278361
294 1 222177712
615 2 89635596
635 2 40825083
199 1 75838169
601 2 135555875
535 2 209314915
460 1 95211275
524 1 123964405
536 2 135768485
647 2 86843211
587 1 84422058
370 1 78379100
651 1 238122753
601 2 151044205
647 1 124253452
562 1 198839561
681 1 59596479
444 1 66240624
562 1 165633439
663 1 101109927
632 2 306753355
205 2 70062580
499 2 95599173
436 1 73225387
557 2 297678161
301 1 24069151
432 2 72520202
438 2 66015356
650 2 122246232
638 2 235308147
658 1 100066862
398 1 51658706
250 1 83044814
345 1 66303880
352 1 81189578
673 1 100172495
328 2 135654822
499 1 100898108
526 1 163666094
484 1 186630885
628 2 110269414
638 1 169251045
616 1 122356582
190 1 155240265
561 1 84116183
615 1 78188292
616 2 192028606
644 2 220769764
373 1 70122795
144 2 102044469
667 1 36750707
674 2 117999523
484 1 186201996
684 1 50941502
349 2 340927963
690 2 93258602
337 1 394954030
599 1 110290093
573 1 194719097
580 1 56609819
531 1 317900410
404 1 135199466
554 2 82191127
725 2 204756510
704 1 70896466
574 1 194802712
467 2 232264358
445 2 56207264
501 1 279146191
598 2 69816536
449 1 43106444
720 2 97419124
694 2 112789905
580 1 131876756
626 2 129649079
468 2 18415689
631 2 162163266
330 1 95901958
726 1 307147994
322 2 101247021
645 2 61748747
276 1 159526531
438 2 364665658
462 1 136181522
688 2 131283301
613 1 175164804
429 1 526702426
735 2 166166058
721 1 214579810
656 2 112418033
540 1 27872988
637 2 127166725
755 1 75343271
507 1 134478966
722 2 172723038
534 1 195957815
305 2 44043203
684 2 168061202
602 2 294149512
553 2 141640794
654 2 212772329
542 1 37077795
694 2 371722433
723 2 207970907
313 1 158944412
585 2 42648247
321 1 317288229
445 2 115816128
430 2 97308284
487 1 111238826
767 2 32783213
674 1 44646250
568 1 67003040
548 2 279066120
531 2 156035469
708 1 270408459
307 2 162714799
489 2 37244683
631 1 112687803
649 1 89497188
278 1 29967844
74 2 137251829
312 1 642677778
721 1 520121528
357 1 145490833
681 1 85586840
697 2 31824164
704 2 196489662
228 2 91807928
648 2 48423635
115 1 64522300
567 1 139221583
797 1 63992749
336 2 46131281
680 2 218894673
711 2 271043533
653 2 105650024
574 2 407502572
416 1 65285950
659 1 52148603
179 2 132437527
738 1 154696586
668 2 32502647
507 2 72407322
395 1 78707246
781 1 199432558
251 2 161126943
705 1 31720324
747 1 170136418
699 2 26305048
800 1 114594877
400 2 103467716
678 1 512428010
359 2 225033648
767 2 46218472
353 1 68948233
764 1 115319111
630 2 325857103
650 2 85041281
764 1 203693149
277 2 85608045
791 2 74361040
677 1 154181407
429 2 40578845
169 1 23036382
795 1 204210658
545 1 44568299
465 1 112950259
401 2 16070175
723 1 93276517
652 1 33355937
539 1 34746890
810 2 57477485
730 2 139586946
123 2 10918793
351 1 119575041
775 2 151112155
773 1 123557719
596 2 156011319
322 1 207931746
741 1 48136693
382 2 100453463
852 1 59486420
633 2 125382843
810 1 158290937
692 1 48172292
796 1 133344762
715 1 105753493
778 1 47773106
238 1 22268715
456 1 151521502
468 1 21583849
590 1 128008878
724 2 172503685
618 2 86368239
851 1 77915175
744 2 57133734
623 2 67169703
827 2 265053180
785 2 193369786
761 2 131375286
528 2 128527281
784 1 244925970
266 2 395237827
595 2 329732178
842 2 85408877
623 2 50098115
702 1 201994909
504 1 34900982
646 2 141779894
802 2 308384679
476 2 16877037
666 1 98530569
817 1 179590775
544 1 246067209
520 1 112710868
614 1 130518695
709 1 364831857
868 2 42365049
843 1 438737923
838 2 85474794
633 1 87182963
599 1 108008365
800 2 90209978
666 2 44655447
732 1 111954492
655 2 235092057
832 2 64373820
347 1 85794278
766 1 213587611
686 1 109970661
894 2 100917208
842 2 210492416
403 2 78565777
620 2 198838657
304 2 66367232
420 2 208931882
173 2 119456266
793 1 164992943
743 1 478393154
585 2 48427001
341 2 21322046
801 1 107927445
595 2 77337633
588 1 86599275
913 2 163627223
161 2 85364638
716 1 88231801
568 2 103723557
877 2 32641211
558 2 145665833
777 1 139708684
920 1 132760115
697 2 140356440
790 2 207416595
395 1 174080952
185 1 284314170
797 2 178110257
920 2 104671221
649 2 35267100
332 1 75563175
785 1 88498957
669 2 162684049
511 1 524760811
350 1 88904570
899 2 130870539
818 2 299149634
453 2 26750369
914 2 238636050
779 2 21921242
882 2 53557983
935 1 244433953
722 1 236610966
488 2 102877639
856 2 119445452
825 2 92494514
758 1 246067500
266 2 285145912
663 1 33977637
287 1 188013147
273 1 35995345
776 1 40145126
516 2 38201564
951 1 23399677
845 1 20548029
842 2 72671369
930 1 92023943
940 2 181179675
346 2 63527477
766 2 185943920
778 1 238220520
752 1 182969999
432 2 69541510
435 1 80787879
640 1 174264729
802 1 82290404
865 1 214670806
772 2 140097968
942 2 88469916
279 2 258273132
453 1 43869716
645 2 38042522
183 1 58580779
889 2 96078463
720 1 68342678
746 1 73015754
938 2 38378145
868 1 97148190
514 1 51078929
642 2 170689638
425 1 34847702
485 2 183761465
620 2 151886775
672 2 103339710
569 2 217865862
573 1 137566403
979 2 86319595
825 2 231822435
750 2 198999341
514 1 53348615
751 2 58173610
798 2 249106700
928 1 153466410
932 1 121752213
863 2 271105724
698 1 147183667
677 1 129615856
333 1 386020109
983 2 531674830
748 2 85796000
446 2 266976001
837 2 110460057
945 1 117710640
534 1 70535981
788 1 42318465
917 1 144201422
151 1 184535462
837 1 173022586
630 1 300575112
971 1 68717987
397 1 19820417
602 1 165778991
1003 2 89837617
555 1 69758224
841 1 39753427
930 1 192220295
834 2 71751855
941 1 149749647
696 2 65688500
951 1 28169777
1015 2 151773614
598 2 66954887
257 2 119174146
740 2 37161107
455 2 324457662
730 2 95058408
487 2 258209698
876 1 224889032
964 1 90128438
833 2 184938166
880 2 248836012
781 1 79763919
710 2 280629126
728 2 205553998
761 1 36418515
782 2 56806614
783 1 53496769
906 1 89219083
530 1 211267057
788 2 185910601
786 1 158270996
917 1 188287672
741 2 56209072
809 2 108415576
459 2 163554083
969 2 55030629
851 1 50719706
835 2 65206431
935 2 102635574
1012 1 166334784
972 2 64801074
341 2 15591822
882 2 82408895
981 2 50538075
618 2 51465200
735 1 178592534
1016 2 139831025
961 2 129756440
746 1 58302178
561 2 124204961
1005 2 143939336
243 2 137087941
434 1 98398907
940 1 81391915
669 1 111476055
827 1 151186872
941 1 67968537
981 1 86251305
130 1 163269870
661 1 54259412
625 2 69056710
841 2 118091622
1048 2 230214422
719 1 122801013
632 1 166353759
808 2 554403712
492 1 187209385
963 1 107226898
690 2 254701312
973 1 23901720
1063 1 47290114
411 1 45259732
991 2 72476172
1048 1 60849551
915 1 310226307
1067 2 304913006
1011 1 32677931
912 1 41937009
714 2 236698670
1064 2 222451393
457 1 200856662
617 2 105875181
532 2 63988619
976 2 87658021
924 2 410009385
804 2 47131009
481 1 537373550
1036 2 122761026
679 2 109887145
1060 1 66361689
991 2 61504581
1035 2 83181036
879 2 67677653
839 1 86270158
716 2 54930791
719 1 221953348
367 2 85844231
1104 1 75813011
1037 1 246257748
990 1 229120017
600 1 76369093
644 2 172732686
324 2 125340469
1084 2 93692769
1082 1 247854487
640 1 297309967
1052 1 32586431
839 1 53747301
971 2 37051298
461 1 103205715
815 1 72971848
845 2 26516033
898 1 190397631
826 2 107353850
959 2 90860583
866 2 44208062
772 2 133941058
1098 1 255689782
1074 1 169231073
931 1 43257226
1110 1 167197695
979 1 162488970
1004 2 55843509
1018 1 80327292
960 2 80492662
1070 2 356009429
1087 2 134768368
1022 1 62134375
924 1 55354115
852 2 76781572
862 2 58033862
1032 1 204188297
1043 2 71529056
556 2 34009967
784 1 220473998
744 2 99467718
1059 1 210148350
571 1 138404400
1110 2 340102139
1032 2 128146462
1037 1 173008963
911 2 69900329
974 2 265434355
904 1 103021786
1059 1 223819253
835 2 32196271
984 1 63836031
1118 1 58126651
1014 2 78184877
389 2 153948795
602 2 54033693
317 2 39090514
540 1 25194982
1082 2 61611738
1104 1 349273153
186 2 148880386
987 2 96227815
1160 1 98264120
977 2 37321373
650 2 143517872
1167 1 87991090
1156 2 23639839
836 1 324697595
567 2 73942745
1096 1 82236473
905 2 352490693
261 1 18882163
877 1 83214842
1161 2 352609451
908 2 146572565
1094 1 207470619
578 1 131887754
1125 1 135297993
1162 2 397544969
560 2 47395653
978 1 195681886
886 1 55910598
740 2 55108774
1172 1 235359513
1061 1 132251001
1010 2 186290929
1053 1 30857159
1141 2 266690539
1067 1 162771088
1104 1 54555928
1149 2 304366528
653 2 43017633
696 2 136254119
887 2 355763417
1138 2 54630656
1178 2 69996553
585 1 309022963
1111 1 126354294
122 1 78836918
1038 2 81296473
931 1 80944617
793 1 84247236
1205 2 391186244
1203 2 174967319
1188 2 57946667
1152 2 150311576
1083 1 99044018
853 2 187990733
1141 2 121093300
1192 2 209131911
668 1 16702634
1080 2 26543177
1206 1 74207689
738 2 167277002
1191 2 182213931
892 2 117776835
1042 2 180077934
976 1 62161705
1080 1 65905973
593 1 162049833
351 2 168394218
953 1 189010003
1195 2 105132224
834 1 108321651
692 2 45878048
1166 2 207855813
1029 1 162355997
1219 1 166793301
1005 2 130461257
703 1 298804785
1188 1 120394407
813 2 32755482
867 2 403989756
825 2 146470826
1139 1 155988728
1207 1 281443704
779 2 117373615
952 2 200406297
1189 2 145870936
776 2 86063474
672 2 61275275
829 1 166632712
423 2 35236987
821 1 95620981
592 2 69549176
914 2 193543457
1246 1 117912609
860 2 14978769
871 1 61569894
688 1 66139956
1101 2 162840954
545 2 73242052
1019 2 183140276
1086 2 263218850
873 1 303125158
317 1 152909173
1143 2 55134461
1014 1 68060218
1120 1 151236679
153 1 173775902
1163 1 71853335
945 1 267709903
632 2 232037801
940 2 424674130
860 1 67579748
916 1 493359297
1107 1 81494192
107 1 48353683
1051 2 69428185
1266 1 99269678
343 2 180416634
810 1 120727065
1261 1 143304651
1140 2 151880076
652 2 57929441
646 2 172720077
1274 1 51593395
742 1 306305090
393 1 25805913
1052 2 30121153
1204 1 43899657
1214 2 258191121
708 1 310433649
733 1 217957540
415 2 179045753
1285 2 63447917
1270 2 27647628
1011 1 24646227
799 1 79019405
976 2 294835644
1253 1 59884284
854 1 218777596
505 1 226802946
1218 1 150149548
1288 1 310317078
787 1 153288051
879 1 149000634
846 2 82413026
1109 1 225565260
1282 2 268410127
1257 1 82496710
638 1 204141944
1132 2 130195237
1172 2 154763284
1162 1 127859424
1275 1 275543548
832 2 126623432
1089 2 276136470
1197 2 98303864
354 1 69224653
1227 2 197375814
1159 1 148284800
1163 1 60353660
269 2 128800294
1048 1 59410177
1038 2 93245347
268 2 121767270
667 1 96942224
1053 2 123020725
1158 2 66348150
1159 2 217729024
1126 1 187540449
1282 1 158739793
953 1 237322422
1312 1 106167534
1078 1 223968869
1215 2 237724867
1175 1 41573124
102 1 27537179
1148 1 286047162
956 2 47777214
751 2 41889447
551 1 229839411
1198 1 130726184
1040 1 62990935
1296 1 402967209
1023 2 40736815
821 1 67394866
611 1 31117013
1198 2 93011506
791 2 23410411
1183 1 164582170
1323 2 223487422
783 1 191735201
816 2 162716629
841 2 45838412
987 1 159019703
1342 1 268152098
1201 2 34251428
527 2 674392432
1321 2 103049725
1193 2 117168543
315 2 229300944
617 1 137431193
977 2 114503272
813 1 47811026
1049 2 407873985
1092 2 225609282
1346 2 107908887
1361 1 76904821
1320 1 63920372
1365 1 224115982
952 1 154020770
894 1 136060141
759 2 69634161
1351 1 48633028
807 2 58958900
1364 1 206931567
1237 2 113013768
1286 1 30094708
1309 1 109141195
682 2 103987909
949 1 103845429
989 1 148167581
1035 2 37415540
401 1 29922593
1024 2 111146753
1275 2 125670502
1344 2 190805834
1365 2 102641390
906 2 63363521
1092 1 123116628
72 1 27323252
1010 1 103403314
1341 2 49925657
1225 2 130459068
811 2 317554463
809 1 68532226
1178 1 106255474
1388 1 57358958
954 2 85225383
836 2 238653373
1390 2 120108141
1167 1 96671678
1174 2 232562045
1393 1 58680121
1085 1 99624761
1401 2 167807316
1380 2 260079783
1375 1 53369308
1286 1 26669948
1070 2 53553165
1369 2 264004405
225 1 39235795
968 1 206295095
1120 2 124182417
1068 1 124467018
814 2 98616443
493 1 163934725
1147 2 284649083
1039 1 225702890
1343 1 136810722
1220 2 489043384
1115 2 557292155
853 1 70355314
1121 2 94971007
1261 1 131989538
1105 1 99884338
1383 2 72301351
807 1 79922641
1117 2 51614694
815 2 51390161
1302 1 74936902
887 2 82610014
1358 1 237166484
1138 1 59201291
1046 2 161527913
1263 2 174251962
1230 2 99984957
1351 2 47701389
1088 2 95781262
1368 1 115210274
1344 2 39875800
801 1 42077324
1374 1 108652105
1177 1 83787078
422 2 80161820
1280 2 43788984
1025 2 73585242
1063 2 114969333
1103 1 130974477
1170 2 116926575
964 2 51776530
795 1 127654355
1430 1 113148803
972 2 58506882
1121 1 506170896
1068 1 71565236
1386 2 130931741
587 2 59933782
1081 2 89950409
1349 1 168500127
1439 1 122112994
706 1 182232130
1358 2 175210468
556 1 22060723
1318 1 73138513
1250 2 84961054
1412 2 121088144
790 2 99187762
1216 2 23891199
1323 1 298453985
954 2 50793091
1435 2 173939023
1230 1 318568484
548 1 80817343
1000 1 215189886
1293 1 57358024
1473 2 123346473
1055 2 116642411
990 1 49292414
1217 1 134331551
1405 2 285871892
1396 1 174587996
1047 2 97470916
987 2 125108949
1451 2 78849264
1307 2 135718346
1158 2 240207777
1354 2 119083218
1096 2 80882517
1378 1 115858516
1462 1 77389900
1422 2 135412464
1133 1 136420901
1281 2 159129467
1463 1 150380134
1264 2 126915020
1405 2 210878646
1407 1 207695403
1461 2 127539187
1310 1 84492367
1170 1 28608528
862 2 69690732
675 1 96269695
605 2 221256721
1473 1 107602057
1461 2 75723469
1257 2 52245237
1445 1 142307419
987 2 152069236
1436 1 99373022
1370 1 219113193
1112 2 82711261
1197 1 96989761
1123 2 191336224
1043 1 51060930
1474 2 288703716
1502 1 98619733
980 2 117374375
1224 2 147000086
1426 2 76886454
535 2 416934069
1435 1 86246850
1395 2 195532885
1445 1 152001374
1438 2 67049665
1373 1 216175221
1065 2 299250789
1102 2 137782198
1356 1 74168861
1482 2 115259425
1320 2 180301761
1078 2 318173893
1204 2 32671789
1250 1 228055738
1308 2 72478344
1394 2 287450338
1409 2 34682112
1406 2 126303471
1512 2 97243684
1502 2 101002399
1270 2 45562069
1498 2 142459282
1468 1 50063092
1379 2 125616865
1114 1 97208835
1443 2 67836503
1425 2 317913174
1191 1 240576315
1446 1 106513554
1175 2 214152077
1521 1 289412245
1439 2 89528740
1242 2 125220635
1130 2 151815926
1488 2 249593668
1051 2 48275814
472 1 121973953
1442 2 136687957
1296 1 42799321
1334 2 49289173
592 2 43676117
1451 2 99828055
1040 2 323042542
642 1 122950853
1263 1 179758197
1143 2 126495781
1559 2 136523457
1530 2 48858023
1536 1 73620223
1280 1 64883378
1474 2 206805794
1306 2 131747928
1113 1 192758790
1020 1 58238070
1534 2 88084040
975 2 228401193
1160 1 84019056
675 1 103323673
794 2 443284486
1366 1 241755915
856 1 63209867
246 2 107510759
1535 2 129138515
1118 2 236171409
504 1 25886461
1543 1 118208557
1569 1 181642454
938 1 67291305
1185 2 53058038
1454 1 61976316
1482 2 132607493
942 1 116902426
1381 1 82451800
1293 2 46121693
1004 1 177070515
1205 1 168578366
946 2 228947369
600 1 46095754
1458 2 85423551
1520 1 107926916
1319 1 190652650
1595 2 248665455
1563 1 290831182
1466 1 127039658
1465 1 131267433
1081 2 136855529
1341 1 52818949
1496 1 43038762
1363 1 136267331
1507 1 90130916
1510 2 141897624
955 2 84325849
1558 1 195600941
1002 1 62724528
1455 2 91587118
1146 2 175830614
1380 1 118265950
1319 1 116879663
889 2 132437658
1320 2 340627433
1284 1 25270278
1224 2 56772777
1071 2 87966738
1137 1 136419439
1291 2 50895923
1557 1 22427005
1504 2 219932016
1433 2 143108594
596 2 126083259
442 2 89637592
1321 1 283481213
1559 1 312665038
1262 2 103563544
706 2 134027667
1500 2 146142954
1582 2 82386122
458 1 484385712
1108 2 90895004
1017 1 229041990
260 2 169571190
421 1 115796471
1586 1 70684096
1455 1 276725841
1589 1 166063770
1454 1 205052226
1274 2 122359324
1516 1 66382851
1517 1 223414167
1245 1 252111483
1146 2 100136698
1337 1 93843819
1195 2 52552972
1103 2 71658755
1273 2 51143568
1476 1 264492918
1216 1 117415372
1219 1 308904678
1592 1 348088026
1431 1 90637989
1374 1 129579246
682 1 88614494
911 2 90257322
1245 2 45328631
1470 1 212083708
1537 2 322529530
1477 2 446262389
1589 1 229864263
1653 1 78400885
1254 1 105846661
1331 2 290940570
1169 1 129499375
1512 1 159522650
1627 2 179921457
1653 2 184806039
804 2 31826454
1371 1 193960734
1364 2 77891083
1340 2 313250026
1100 2 182201877
1177 2 87087956
1661 1 123358522
551 1 112868436
1315 2 95549175
765 1 114945469
817 2 161191244
1462 2 411239176
1677 2 48486970
1621 1 197903976
1154 1 145051733
1113 2 60970326
1547 2 292616398
648 1 93394138
1578 1 110128899
1619 2 62329649
1561 1 180423932
1626 2 206814911
1649 1 64167245
1515 2 220853747
1262 2 97230536
1459 2 149625070
1499 1 249902000
1528 1 111404292
913 2 218286842
1622 2 120797916
1643 2 154266042
1553 1 59092465
1134 1 254540296
1633 1 42259849
1405 2 48876741
1152 2 102141948
1486 2 349902658
699 1 107259536
1144 2 68950094
1253 2 26534498
1571 1 121150973
1111 1 299150851
1360 1 80573131
868 1 110886477
1324 2 135419354
1570 2 100623823
1448 2 268879988
1691 1 248990632
1644 2 282664535
1607 2 247038544
1637 2 191717868
1716 1 191020728
1662 2 208690685
1615 1 260950996
1248 2 43749725
1420 2 214765444
1555 2 133046825
1557 1 55287619
920 1 92316330
1446 1 188604330
1272 1 70404302
1549 1 144228128
1102 1 67876421
1088 1 19393424
1540 2 106347346
1118 2 102026718
1729 2 80075442
1534 1 28561719
1162 2 46724624
1728 2 95879025
1126 1 114428861
1279 1 138247572
1047 1 53440569
1538 2 65217082
1480 1 107834844
1630 2 206376754
1745 1 117859133
1412 1 117669869
1144 1 131296357
1234 1 214785265
1468 1 77428326
1054 1 81997585
661 1 71277921
912 2 40325833
1284 1 112218968
1689 2 84441809
1736 1 332608306
1582 1 78744065
1532 1 264692661
1623 2 72665913
1428 1 112792828
1021 1 221062169
1619 1 193710031
1049 2 302987254
1530 2 54028974
698 1 79430157
1639 1 132125257
1669 1 269200956
1119 2 54631116
1712 1 99646621
1609 1 35088597
1538 1 35054062
1085 2 119861901
1337 2 52151443
1761 2 182792544
1015 2 37572399
1726 1 101109221
1395 2 198225385
1752 1 76174346
1132 1 108803028
1591 1 74096047
1729 2 74288863
1757 1 179747105
1539 2 232955094
1186 1 237135253
1773 1 223967978
814 2 39528894
1620 2 95215222
1629 2 108838168
1593 1 185078363
1579 2 52494441
1604 2 54302675
1635 2 167973578
713 1 142476826
1673 2 146165660
1367 2 369550862
1677 2 192638123
1759 1 137582330
1665 2 127848001
1325 1 298980652
963 2 23615168
1386 2 67524564
1730 2 174237198
1137 1 189252778
1761 1 210453053
729 2 94617175
1650 1 139499505
1525 2 178816475
1651 1 130818013
1318 1 115175574
1468 2 306520911
1471 1 69209509
1622 2 266920484
1618 2 123262803
1799 2 106732312
1504 2 103787929
1257 1 72406536
1555 1 46037446
1599 1 217339268
1501 2 161980613
1378 1 174386104
1784 1 301948542
1565 2 165337452
1750 2 33390563
1553 2 235992043
1470 2 140570906
1333 2 171938690
1781 1 144902375
1237 2 79603640
1779 2 81632999
1672 2 118136190
1044 2 254297126
1509 1 287677946
1711 2 26540821
1825 1 78415313
1668 2 220962363
1192 1 283719174
1762 2 120430579
1689 1 112838922
1554 2 303948091
820 2 105150880
1833 1 153593686
665 2 131879815
1800 2 134830357
1382 1 213104402
1486 2 93093967
1503 2 112761123
1605 1 91551947
597 1 85807070
1674 1 223213849
1291 1 66918962
1767 2 163237893
1648 1 157094637
1572 1 132591367
1802 1 265183835
1684 1 205675202
1787 2 137039945
1750 2 87718550
1660 1 297506474
1164 2 237971617
1317 2 86417553
1824 2 158423556
1739 1 180259112
1471 1 220975289
1859 2 130274600
1775 2 71169256
1675 1 564362799
1775 1 201638990
1436 1 112074031
1372 2 125972106
1687 2 85925302
1672 1 182779993
1696 1 121383701
1755 2 71745849
1856 2 103424596
1480 1 194051748
1136 2 136512068
1479 2 296207354
1199 1 139965467
1587 2 244058640
1567 1 146183668
1578 1 113176128
1793 2 66621741
1563 2 234276628
569 1 88737501
1666 1 84812952
1730 2 142385427
1140 1 169321914
1453 1 340976406
1096 2 168151570
959 2 67761482
1535 1 132922683
1659 2 154851163
1755 2 28442126
1782 1 68147789
1384 2 117072586
1540 2 148153796
1832 1 120635821
915 2 167610335
1756 2 61771957
1396 1 109979672
1413 2 134506958
1799 1 188438331
1754 2 27544459
1567 2 67995241
1787 1 220610270
1738 2 62164325
1292 1 85675455
1864 2 80774331
1384 2 108757215
1242 2 148411754
1806 2 233564190
1854 1 287418999
798 2 125948491
1266 1 59165327
1814 1 153440067
1765 1 69254147
1852 1 63320907
1753 1 323763325
1579 1 29613915
1390 2 71522663
1685 1 334954645
1710 2 132289960
1766 2 179831226
1748 1 169457656
1778 1 79962361
1906 1 102622150
1916 2 166134208
1466 2 91580090
1710 1 41059029
1855 2 99912475
1671 1 152303580
1646 1 92590689
1737 2 284447580
973 2 47072177
1911 2 145734673
1808 1 176076502
1580 1 109429904
1803 2 331821208
1840 2 115472575
1359 2 324561267
1477 1 143739842
1813 2 139389234
1462 1 230376233
1622 2 225726800
893 1 557916587
1737 1 196043681
1663 1 106332981
1948 2 354184229
1595 2 141030790
466 2 141325031
748 1 269363753
782 1 142680091
1609 1 36039528
1618 1 71061176
1434 2 200570256
1359 2 166012795
1955 1 36464996
1792 2 124661633
1815 2 146513727
955 1 23145507
1457 1 130098793
1960 1 187521826
1517 2 28174750
1896 1 134414297
1824 2 117988709
1169 1 138690326
1679 2 179207433
1621 2 103751799
1902 1 105662865
1770 1 180272181
544 2 216509962
1650 1 271152826
1360 1 174140564
1574 2 148201461
1568 1 317316266
1919 1 181654614
1588 2 129591561
1185 2 54735264
1912 1 250574812
1166 2 266669812
1054 2 116469868
1930 1 144263281
1847 1 193850664
1122 1 42464042
1895 1 67217840
1788 2 248485188
1921 1 100713701
1961 2 76967365
1388 2 58655823
1215 1 240497895
1565 2 166637608
1987 1 175183571
1798 1 112050919
1893 1 73555237
1601 1 190487998
1441 2 97506573
1885 1 83036166
1652 2 110567124
1909 2 96137240
1980 2 66639804
614 1 55507578
1895 1 70699839
2001 1 129516630
1519 1 162610051
1315 1 66882308
1393 1 159613853
1389 1 114990657
1972 2 107638519
1875 2 38940193
1026 1 130912691
1703 1 141397177
1850 2 107159851
1830 1 193294126
1087 1 25466430
1778 1 385133848
1815 1 152116678
1610 2 147835107
1980 2 199340709
1832 1 172458963
1351 1 254501465
1921 1 47080371
1750 2 306367333
1603 1 201309431
1931 1 188414538
1811 2 152626162
1882 2 236723261
1756 1 66995817
1772 2 69857727
1067 2 367572150
1590 1 66755337
1596 2 177679075
1680 1 108107230
1665 2 138436372
1022 2 53080694
2007 2 182098677
1958 1 87384368
1684 2 40869800
1044 1 114726814
1955 1 26767038
1899 2 80461407
522 2 65524479
1605 1 187368855
2016 2 99871190
1783 2 147092007
1961 1 169343627
978 1 76481098
1744 2 52327482
2046 1 94516010
1825 1 140280178
1084 2 89762182
2011 1 92456382
1766 2 64120774
1638 2 94227975
1669 2 111353251
1886 1 153161714
957 1 159162885
1476 2 388294456
1361 2 74148878
1543 2 191487212
1023 2 170309518
2061 2 164152779
1707 2 194898696
1768 1 108035014
1956 2 207205620
1556 1 92856869
1967 2 192611299
1803 2 147773836
1734 1 107067627
1590 2 32703943
1556 2 45403806
1348 2 209024960
1633 2 69725878
2055 1 319184572
1770 1 131794909
1987 2 92415048
2048 2 103539513
2018 2 63153068
1973 1 189343421
1372 2 344071703
1507 2 234551085
1901 1 84008750
1879 1 194227384
2007 1 196851130
1726 2 56891424
1631 1 113082004
1936 1 39954883
1312 2 102153513
1922 2 112092644
1639 2 78943041
1122 1 49192898
1889 1 247476704
1479 2 148477751
1441 2 42891938
2088 2 40513777
1867 2 81471495
1711 2 23595595
1426 1 152626275
1519 1 863870265
1659 2 98425698
1680 2 103229421
1748 1 110776765
1101 2 138497459
1768 2 80312992
2047 2 365348808
871 1 39137907
1746 2 221284580
1380 1 142170603
1723 2 74067939
1314 2 104278208
1993 1 82930925
2096 2 280953328
2099 2 157573069
2032 2 98288513
1973 1 98998606
2071 2 175803898
2092 1 40338646
2066 2 132258651
2031 1 219805877
1927 2 115029244
2101 2 166823468
1496 1 74790842
1709 2 143170747
1982 2 108198796
1585 1 151883387
1650 2 124917774
1852 1 60462173
1836 2 366776981
1604 1 134232031
1802 1 97596621
1442 1 77919030
2098 1 193953662
1840 1 292769521
1018 2 99217667
1434 1 26305170
1752 2 79270960
2051 2 175311699
1217 2 81017732
1883 1 167712243
2016 2 113303642
1833 1 49569635
2060 2 149757894
2036 2 217470469
2133 2 107710298
2096 2 230901988
1924 1 164882013
1499 2 96462877
1701 1 138261489
2071 2 226028001
2054 2 159448579
2029 1 57114862
2143 1 87771965
1338 1 275253126
1658 2 82098791
1021 1 75065425
2048 2 204801962
635 1 27580462
741 1 120266415
1859 2 160392313
2139 1 43581815
949 2 142752041
1892 2 69794066
2002 2 164319574
1619 2 272140487
2091 2 77350677
965 1 183598376
659 1 48531986
2107 1 85110824
644 1 87951133
2141 2 181975962
2132 1 85900652
1959 2 74196290
1514 1 190538212
2104 1 119833762
1536 2 59464727
1292 2 22354856
2045 1 140998534
2072 1 72198044
1474 2 112272361
1014 2 124004131
1672 1 72258741
1035 2 487557331
1585 1 83406611
1187 1 201874837
2069 1 146253231
2103 1 319113615
2089 1 194092165
2004 1 195891187
2177 1 156987503
2083 1 78926359
1882 2 431801194
2054 1 90502797
2160 1 107025257
1943 2 259726939
1991 2 30899188
1712 1 122601245
1456 1 299684398
1998 1 165272544
2044 2 345623210
1910 2 197077510
1991 2 150162230
2126 1 164127402
2158 1 74521914
1713 1 129312269
2132 1 162534969
1427 2 84856831
1766 1 221137508
2078 1 222245880
2161 1 381660215
2053 2 124995084
366 2 25084813
1285 2 112362306
1438 1 148891787
2177 1 111932066
1752 1 107339920
2092 2 35060815
2190 2 195595182
1083 2 291683854
1907 2 82481407
2095 1 148095670
1024 2 82481437
2173 1 97142009
2132 2 60426475
2118 2 68600667
1908 2 162753609
1345 2 82107384
2056 1 238401165
2135 2 194915908
2113 1 429298323
1892 1 24558054
505 2 122152062
1777 1 131789565
2182 2 140870943
2190 1 95089283
2074 1 246774924
2147 1 283634023
1984 2 45739028
1583 1 205938320
2139 2 57389311
2146 2 339362527
898 1 69630526
1855 1 85862515
2098 1 44459059
1546 1 339105585
1757 1 142365690
1994 2 210877405
2060 2 214886706
1019 1 64127382
2072 2 96558556
1878 2 162716405
1941 1 238325516
2246 1 71788069
1960 2 154426895
2152 1 272861794
1421 2 176711995
1816 1 167356799
2222 2 208158467
1959 2 105755212
2041 1 101827257
1754 2 194204938
2249 1 59265351
2009 2 121485213
1909 2 66146070
1805 1 80643243
1428 2 78217575
2213 1 51807597
2207 1 188210618
2162 2 281144497
430 1 148820821
1773 2 38704151
1421 1 48176810
2074 2 123309783
1623 2 69123030
2177 1 67508224
2185 2 464705771
1705 2 264888601
1156 2 102736644
2179 2 335233995
2041 1 101994509
1777 1 202128111
2244 1 129983950
1792 1 21983426
1738 1 75411259
1558 2 163998732
2212 1 97247121
2115 2 173165802
1735 2 55243938
2221 1 179534697
2208 1 132563026
2168 1 97558406
2053 2 118040192
1406 1 40439468
2288 1 290945713
1429 1 102619171
2184 2 316710554
1989 1 82243701
2098 1 64011097
1870 1 217946828
1188 2 83714848
1601 1 91455423
2271 2 33944980
2293 2 268274947
2094 2 243733618
2248 1 211669523
2219 1 104677702
711 2 322527203
1986 2 22785524
2030 2 68708792
1572 1 132432476
2016 1 236288589
2298 2 90171308
1922 1 127349173
2203 1 191406918
1916 2 125362858
2217 1 66232575
1107 1 273945711
2083 1 88994773
2088 2 242192721
2317 2 249205495
2173 1 168359048
1149 2 194238181
2005 2 163190108
2288 1 103369492
1591 2 148518086
1705 2 137081511
1346 2 66763020
2283 1 101557774
1938 2 98445130
2280 1 211847613
2234 1 137309577
2267 2 320828097
2260 1 283778027
1759 1 95529140
707 2 322685313
1932 2 93696771
988 1 158142504
2130 2 289283001
2310 1 147432556
2281 1 248219354
1962 1 71224568
2265 2 178038018
2067 1 177049757
1571 2 84619627
2268 1 353597477
1302 2 87951829
2030 1 71382414
2032 2 153516403
2161 2 105584431
886 1 38165800
2314 1 167628672
2350 2 295161563
1635 1 121677559
1694 2 205040183
1248 2 53454546
1255 1 114242443
2344 2 139605863
2325 2 86023786
1229 2 195398416
1387 1 293872169
2290 1 215387641
2079 2 82284049
2109 1 440793897
2291 1 60695761
1998 2 112056853
1830 1 60506028
1827 2 99120341
2215 1 155764083
2319 1 211370867
2027 1 342256324
2039 1 93850747
1254 1 259587770
2095 2 259364591
2243 2 130667739
2286 1 204000259
2242 2 134242284
2118 1 37159588
1782 2 144905012
2341 1 23958757
1864 1 160922315
2377 2 305046859
2066 1 160001439
2340 2 207443268
2001 2 50105325
2286 2 78096809
2196 1 199748613
2163 2 146750502
1875 1 45333352
1971 2 112461478
2266 2 65193947
1349 1 110331205
1389 2 138616559
420 2 87933613
2352 2 279263882
530 2 205261039
2357 2 92674012
2095 1 138392965
2382 2 140687607
2310 2 114156107
2393 2 398018558
2086 1 225765348
2158 1 61094907
2326 1 236059723
2381 1 149914185
1381 2 96279136
2327 2 58601958
2316 2 77874151
2012 2 119093055
2169 2 210102613
2260 2 130381830
1516 2 434786379
1805 1 324793889
1125 2 108078348
2204 2 107876439
2405 2 134935370
2415 2 176933141
2049 2 97953133
1968 2 154659462
2365 2 143226825
2308 2 93357705
1863 1 327698497
1835 1 52917284
2422 1 214925020
2212 2 92489507
2385 1 84143717
2274 1 207285082
2405 1 101970544
2334 2 173244458
1995 2 191172820
2325 2 332998671
1962 2 121559707
1371 1 150177253
2333 2 158559584
1586 1 91692010
2196 2 382071405
2355 2 53380405
1612 1 124547767
2102 1 194684275
2330 1 116077224
2420 1 61300069
1906 2 149709272
2399 1 128929189
2440 2 194336445
1503 2 98800844
1599 1 254765102
2278 2 139362805
2029 2 78239974
1522 1 189505461
2437 2 161538206
1739 1 62755815
1714 1 361707834
2346 1 164575177
2264 2 227605724
2397 2 251619003
2392 2 274995004
2427 1 152943802
2318 2 441357548
2393 2 190794857
673 2 132718876
1848 2 224512827
2444 2 80885100
2270 2 99731841
2150 1 436825944
2152 2 72500625
1798 1 214287999
2440 1 81114099
1735 1 130349022
2218 2 247378692
1848 2 190391911
1566 1 62695872
2366 2 161436327
2136 2 622404074
1599 1 174172177
2151 1 239819065
2308 1 121154817
2373 1 128157827
2316 1 65628865
2137 2 141394605
2477 2 168219164
2355 1 86617817
2309 2 63724195
2152 2 110862535
2458 1 288253831
2237 2 208664482
1902 1 246243865
2156 2 193020447
2387 1 214265718
1185 1 135862029
2127 2 84561948
2018 2 517950745
2475 1 92850633
1334 1 57388072
2432 2 295899553
2347 1 84445714
1754 1 181284548
2461 2 107179266
1671 1 132641857
2485 2 153155654
2469 2 175045198
2307 1 80077426
2401 1 452215390
2334 2 135694643
2011 2 88193206
1273 2 42583042
1838 2 96028185
2302 1 166526059
2270 1 54084303
2086 1 139169257
1690 1 151123541
1744 2 105681818
2224 1 231771908
2184 2 179217838
2444 2 137148335
2225 2 145110508
2203 2 155649070
2491 1 82195438
2434 2 211790149
2391 2 167554945
2208 1 276997391
2467 1 143557538
1905 2 192720669
2301 2 80142137
2267 2 138437050
2426 1 228739932
2282 2 171108336
2293 1 93626491
2392 2 66871976
2309 2 53088027
1930 1 94853756
1144 1 252742051
1901 2 132694257
2036 2 69968210
2379 2 166041749
1783 2 77594809
1638 1 238066440
2298 1 102153239
2384 2 265353957
2278 2 148572496
2348 2 125985114
1522 2 193174663
2466 2 145842034
2231 2 218665924
2297 2 105627057
2462 2 178198826
2431 2 96289804
859 1 235400636
1956 1 38104361
2273 1 186494176
2497 1 335355591
2067 2 256916759
2192 1 115414885
1961 2 384322278
2315 1 288419435
2283 2 85886530
1657 1 235416173
2346 2 144113347
2341 2 56526875
2494 1 135859933
2328 2 213620393
1883 1 207820076
1535 2 184822706
1993 2 195036597
2164 2 148799250
2492 2 43832625
2531 2 104154756
2452 1 288989014
2182 2 160122306
1275 1 77494875
2534 2 206351199
1858 2 196916686
2002 1 112821702
2512 2 176365115
2217 1 58668857
2533 1 143567052
2416 2 291520334
2234 1 162933039
2259 1 132067628
2213 2 102137273
2417 2 177479906
2312 1 86321604
2026 1 210256945
2254 2 175407618
2086 1 293877232
1965 1 107624673
2462 2 188276052
1931 2 102398381
2148 1 187912655
2467 1 127095254
2225 1 37899176
2450 1 97170672
2023 1 48116053
2293 2 154873812
2085 2 291202110
2533 1 236924244
2556 2 110026662
1205 1 79811861
2447 2 59846454
2578 2 79268287
1427 1 77083860
2545 1 119239203
2402 1 161838452
2507 1 48635791
1990 1 107532547
2325 2 124677318
2573 1 45085278
2300 2 90097962
2428 1 250942158
2492 2 104173443
1924 1 60903034
1108 2 137521194
1443 1 55971034
2590 2 421239665
2456 1 157195851
2441 1 66399582
2264 1 342953794
2547 2 107501634
1993 1 133235656
2004 2 162753260
2480 1 176626271
2285 1 247650414
2344 1 167048844
2259 1 69199860
2422 2 70897079
2404 1 173201178
2567 1 363223093
2589 1 101251982
2262 1 79739345
2377 1 32939613
2431 1 69433124
1811 1 176391314
2402 2 99778526
2628 1 124320227
2280 2 134840468
2481 1 224521886
2516 1 161631516
2141 1 221532945
1347 2 124370980
2379 1 124558085
2514 2 188987273
2529 1 188823822
2605 2 159152625
2491 2 73682174
2502 1 201497856
2415 1 281215420
2628 2 127045297
2520 2 95325134
2173 1 68816215
2600 1 77515292
2459 2 117703259
1870 1 60498828
1706 2 74282861
2610 2 188697332
2522 2 94347287
2608 1 156037779
2611 2 80229859
2578 1 191765074
2617 1 200164204
1229 2 57021771
2599 2 114944315
2420 2 64915461
2459 1 173454407
1648 2 132439232
1742 2 157482496
2647 2 162648627
2531 1 84677974
2645 2 136180372
2597 1 367552856
2631 2 130119493
2410 1 98254475
2638 2 108732341
1980 1 43264568
2671 2 135492845
1915 2 166918101
2616 2 109511246
2447 2 88720577
2578 1 172367259
1989 1 124464131
2605 1 343580223
2123 1 127989954
2660 1 255994475
2204 1 182567770
1195 2 105762437
2388 1 153873323
2679 2 380413724
2618 1 376727725
1745 2 108156251
2600 2 119295473
2611 2 67963549
2590 1 80465120
2514 2 60010239
2523 1 486243992
2102 2 188861685
2671 1 264069640
1772 1 38491636
2594 1 191124710
1986 1 24368446
2693 2 121221761
2222 2 167884746
2636 1 174431280
2696 1 80393406
2510 1 284745205
2672 1 179523293
2608 2 64537278
2639 2 84248378
1409 2 43797520
1636 2 158838851
2316 2 48739546
2694 1 71840669
2683 2 139975656
2328 2 464193209
2538 1 233538825
2507 2 109462939
1936 1 49925571
2565 1 74805639
2412 2 96254600
2235 2 72732746
2705 2 90506829
2712 2 95101783
2526 2 146534518
2123 2 125190640
2623 2 106641800
2447 2 180202371
2528 2 217673664
2659 2 135211811
2671 2 276206638
2477 1 42846308
2708 1 177829800
2347 2 112981063
2681 1 424615026
2589 2 176930029
2107 2 119521401
2662 2 136622347
2003 1 120446463
2450 2 283061059
2609 1 95237263
2728 1 55928359
2717 1 111785739
2215 2 303500035
2724 1 122060406
2532 2 228636155
2244 2 73727639
2564 2 45223415
2675 1 242061604
2436 1 333218990
2649 2 72206684
2464 1 91015516
2690 2 154381455
2434 1 125480946
2045 1 320345591
2632 2 132997443
2185 1 64630782
2694 2 190740716
2368 2 397464115
2655 1 126314779
2742 2 114565568
1117 1 40606422
2197 1 266240795
2475 2 71149232
2686 2 502955953
2629 1 78831925
2571 1 376267857
2327 1 75685030
2271 2 86696502
2504 2 162886563
2554 2 117456445
2660 1 89668827
2604 1 232666309
2023 2 148240277
2544 2 186109726
2615 2 199164339
2648 2 115145987
2752 2 165749886
2766 2 223302676
2274 1 121422247
2343 2 143599247
2737 2 80368072
2733 1 149037552
2703 1 305127738
2388 1 102856895
2602 1 262420830
1375 2 82629777
2748 2 124880014
2507 2 206150715
1992 1 173735407
2401 2 214062397
2504 1 79678043
2564 2 131080234
2741 2 136700943
2742 2 77674058
2503 2 245104983
2686 1 144374182
2778 1 114798555
656 2 52028096
2591 1 78160411
2760 1 93827861
2508 2 98315578
2547 2 293629275
2764 2 85941181
1324 2 178281282
2629 1 124591832
2665 1 223446755
1020 2 60483901
1975 1 141307011
2705 2 99494566
2789 2 243630449
1835 2 74802800
2713 1 70510650
2099 1 86634097
2802 2 112896847
2700 2 106064656
2807 2 212490177
2480 1 295431232
2588 1 161272127
2760 1 249707268
2557 2 117637417
2424 2 121495590
2703 1 124224579
2428 1 166987727
2573 2 99663740
2406 1 378801411
2003 1 134993576
2821 2 221116841
2650 1 90642088
2622 2 325695553
2717 2 90283656
2662 2 188685341
2707 1 70874293
2800 1 165776255
2427 1 136626665
2746 2 79724238
1651 1 70178321
2707 2 92710873
2804 2 71204844
2131 2 109874580
2752 1 167661813
2638 1 237186175
2815 1 222898729
2596 1 200471471
2800 2 54937266
2802 2 50655625
2725 2 65457682
2781 2 97042331
2324 1 99548181
2756 2 96766706
2812 1 251897985
2606 2 347123611
2557 1 83138758
2500 1 183960850
2840 2 193259107
2837 1 258213485
2126 1 342268502
2831 1 152798792
2840 2 79689844
1556 2 215677078
2835 2 344417298
2806 2 64469721
2807 2 99576932
2836 1 270050350
2726 1 223245441
2679 1 78679682
2568 2 73833466
2787 2 105156133
2730 2 304956725
2646 2 137832843
2849 2 74502212
2654 1 75899918
2806 1 115030129
1119 1 107564120
2758 1 174382447
2840 2 96666592
2856 2 139715642
2381 2 276158631
2756 2 60540411
2586 2 251156004
2577 1 466307898
2833 1 361554788
2809 2 78644413
1520 1 181310727
2696 1 65143703
2847 1 103944481
2847 1 115610147
2708 2 106523041
2881 1 53132176
2817 2 525494026
2827 1 268585646
2704 1 235707880
2800 2 169930431
2424 2 169293260
2787 1 77566775
2815 2 142529638
2839 2 129687394
2862 1 235542598
2819 2 336626869
2700 1 64960196
2829 1 460706819
2776 1 96078067
2808 2 75196754
2688 2 1000000000
2178 1 139864416
2679 1 362914540
2833 1 52269934
2793 2 149771481
2605 1 107198573
2879 1 105198604
2894 1 132657492
2415 2 245562605
2882 2 225718158
2758 2 150968916
2787 1 287537695
2670 1 131969800
2901 2 223079498
2869 1 215823894
2713 2 102233535
2855 1 71910555
2809 1 84421275
2319 1 40052703
2873 1 63105362
2888 2 155707770
2844 1 179372282
2795 1 487780166
2879 1 45133120
2921 2 166108966
2737 2 181112864
2759 1 167203196
2917 2 164183472
1989 1 136318611
2904 1 238564304
2868 2 266212480
2545 1 150543712
2654 1 185051221
2929 1 134620964
2825 1 209793080
2786 2 67395446
2894 2 182777137
2741 2 428759338
2832 2 112150036
2598 1 271531982
2903 2 197097775
2804 2 71359984
2315 1 134858247
2866 1 176398131
2797 1 215008852
2720 1 225070605
2877 2 227713718
2935 2 62154433
2873 2 162759811
2939 1 106759816
2789 2 186204665
2903 1 108420715
2819 2 85176095
2849 1 118473582
2946 2 174700893
2915 1 155167999
2810 1 143850462
2928 2 116133250
2168 1 359161596
2781 1 200926830
2810 1 90959603
2791 1 151832533
2436 1 176358076
2950 2 231336057
2941 2 286218218
2934 1 179779923
2913 2 136692851
2921 1 76722931
2904 2 112299762
2905 2 90242144
2965 1 243877358
2960 1 94432711
2825 2 87404135
2904 1 68334383
2917 1 117665476
2766 2 97077617
2923 2 149280623
2922 1 111816802
2958 1 135118159
866 1 137038765
2929 1 241483292
2970 1 66312852
2926 1 148081511
2977 1 174592407
2957 2 238708394
2979 1 221129049
2977 1 208026785
2868 2 136911840
2978 2 311845761
2908 2 116647550
2916 1 218632856
2844 2 158180247
2939 1 150217444
2990 2 113354815
2971 2 136509022
2989 2 186191084
2828 2 97466810
2857 2 212601120
2981 2 151150902
2913 1 98933431
2997 2 199652414
2956 1 54354382
2964 1 99467678