100 1000000000
0 2 60428570
1 1 66827295
2 2 24238861
3 2 32334192
4 2 28224625
5 2 94624940
6 1 77449738
7 1 50072504
8 2 128064792
9 2 54983656
10 1 30104829
10 2 405379841
11 1 129897648
13 2 76542686
14 1 111211868
15 1 38783349
16 2 48425231
17 2 62687740
18 1 58351618
19 1 185804402
20 2 38662398
21 2 198979756
22 1 65234425
23 1 92413100
24 2 71116640
25 1 41708003
26 1 26104441
27 2 74697358
28 1 39552593
29 2 69485709
30 2 66481303
31 1 37195377
32 2 49083552
33 1 72251720
34 1 73589536
35 2 24690756
36 1 46016035
37 2 40782359
38 1 68270143
39 2 61285557
40 1 48574486
41 1 55853446
42 2 59576302
43 2 255645338
44 2 53561764
45 1 112273903
43 1 468533529
47 2 405455292
46 2 71894564
49 1 59428490
50 2 83798879
51 1 95139768
52 2 45818195
53 2 55129600
54 1 64337363
55 1 51535743
56 1 33448739
57 1 162172557
58 2 323600641
58 2 79551795
60 2 121314318
61 2 139420598
62 1 605080149
62 1 47153959
64 1 68702364
65 1 27939265
66 2 72248424
67 1 46366224
68 2 125962806
69 2 121275340
70 2 87432940
71 2 140887931
72 2 936409437
72 2 52003580
74 2 106028210
75 2 94608429
76 2 76107499
77 2 122231997
78 1 412985326
79 1 92475345
80 2 121821047
81 1 95188083
82 2 202222128
83 2 230597062
84 1 110244368
85 2 192183230
86 2 199995726
87 1 79269062
88 1 250376889
89 2 396257995
87 2 514970317
89 1 1000000000
90 1 120147126
93 2 170962598
94 1 386772308
95 2 309923102
96 1 267967310
97 1 430519034
98 1 348329211
99 1 547339718