input:

100000 100000
1 48500 63742
1 43673 89780
1 6471 44388
1 68054 71541
1 30056 91431
1 49687 70537
2 46899 46900
1 5165 57954
1 85892 88481
2 18060 18062
2 45289 45289
1 18927 67848
1 17389 96139
1 63451 92197
1 15473 87341
1 15162 15744
1 76728 99645
2 48730 48731
2 20886 20888
1 9756 67424
1 23175 4...

output:

6
8
8
14
14
16
18
18
20
21
26
26
30
30
31
31
33
34
34
34
35
35
35
35
36
39
40
43
44
44
45
45
46
49
49
50
50
50
51
52
52
52
54
56
56
56
56
56
57
57
57
57
61
63
63
63
63
63
63
63
64
65
65
65
65
65
65
67
68
68
68
68
71
72
72
75
75
75
75
77
77
77
77
79
80
81
81
81
88
88
88
90
90
90
93
96
96
96
96
97
98
...

result:

wrong answer 1st numbers differ - expected: '2', found: '6'