2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
2 1
2 1 27
1 0
4 3
1 2 3
2 3 4
3 4 5
4 4
1 2 5
1 3 4
2 4 4
3 4 5
4 4
1 2 5
1 3 5
2 4 4
3 4 5
5 7
1 2 1
1 3 2
1 4 3
1 5 4
2 3 1
3 4 1
4 5 1
5 7
1 2 1
1 3 2
1 4 3
1 5 5
2 3 1
3 4 1
4 5 1
3 3
1 2 1000000
1 3 1000001
2 3 999998
100 350
1 14 87
1 26 92
1 28 62
1 30 75
1 43 44
1 51 85
1 55 29
1 73 70
2 18 74
2 19 74
2 26 70
2 41 26
2 61 70
2 70 100
2 75 20
3 36 33
3 37 66
3 54 37
3 78 58
3 96 12
4 20 100
4 23 44
4 26 55
4 47 85
4 68 66
4 85 40
4 90 4
4 97 5
4 100 37
5 19 30
5 27 79
5 34 5
5 36 18
5 40 75
5 54 95
5 63 76
5 71 36
5 74 11
5 80 97
6 24 14
7 30 80
7 47 2
7 59 73
7 67 81
7 77 25
7 89 72
8 29 66
8 42 15
8 46 28
8 70 61
8 77 55
8 92 30
9 11 72
9 22 12
9 54 19
9 74 51
10 13 28
10 28 20
10 36 52
10 52 97
10 65 25
10 69 62
10 73 19
10 84 1
11 37 5
11 64 52
11 69 36
11 93 87
11 94 68
11 95 12
12 85 31
12 91 95
12 92 92
13 39 70
13 53 29
13 70 86
13 88 59
13 100 63
14 22 88
14 44 71
14 48 93
14 56 42
14 61 60
14 80 84
14 98 27
15 18 10
15 31 63
15 43 58
15 48 30
15 66 94
15 69 77
15 100 85
16 17 2
16 21 67
16 26 100
16 28 29
16 46 91
16 62 80
16 96 5
17 27 73
17 60 31
17 65 73
17 84 85
17 86 94
18 32 95
18 35 6
18 39 25
18 43 34
18 81 42
18 92 93
19 33 44
19 40 15
19 50 24
19 88 46
20 27 79
20 34 21
20 39 46
20 40 22
20 41 4
20 46 54
20 66 66
20 89 50
20 100 3
21 39 48
21 62 70
21 70 99
21 86 78
22 39 31
22 52 12
22 70 52
22 73 85
22 75 16
22 97 37
23 57 22
23 75 27
23 81 75
23 97 15
24 55 83
24 67 54
24 69 82
24 80 77
24 92 84
24 97 12
25 33 85
25 42 44
25 45 94
25 61 21
25 75 93
25 79 46
26 72 24
26 74 67
27 30 17
27 32 56
27 47 20
27 58 57
27 60 19
27 77 17
27 85 28
28 35 2
28 57 96
28 69 52
28 71 77
28 74 27
28 82 53
28 83 43
28 85 72
28 88 23
29 31 19
29 33 54
29 45 82
29 47 94
29 84 50
29 91 77
30 33 6
30 41 47
30 56 20
30 60 31
30 88 79
31 35 74
31 39 25
31 58 59
32 60 66
32 69 81
32 85 50
32 86 97
32 90 26
33 47 50
33 54 28
33 59 29
33 70 77
33 74 10
33 80 5
34 46 56
34 49 41
34 53 50
34 89 89
35 36 42
35 50 49
35 72 99
35 83 68
36 39 35
36 43 41
36 52 48
36 57 12
36 84 85
37 50 19
37 71 70
37 74 81
37 80 96
37 84 84
37 88 96
37 92 81
38 51 9
38 57 58
38 64 77
38 67 10
38 75 64
38 99 51
39 44 38
39 56 46
39 62 70
39 69 84
39 70 91
40 48 40
40 51 26
40 54 100
40 61 90
40 65 27
40 66 85
40 72 54
40 73 34
40 96 70
41 57 3
41 76 51
41 98 99
42 59 16
42 76 75
42 82 70
43 56 67
43 64 64
43 83 74
43 100 62
44 55 86
44 63 82
44 82 40
45 54 25
45 60 35
45 67 57
45 99 79
46 52 72
46 54 28
46 76 97
46 100 74
47 50 47
47 55 67
47 69 8
47 84 73
47 89 54
47 90 53
49 68 80
49 86 81
49 90 21
51 52 34
51 73 31
51 76 38
52 56 47
52 80 19
52 99 89
53 68 97
53 95 88
54 65 12
54 66 48
54 70 90
54 91 16
55 56 76
55 75 11
55 81 48
55 95 74
55 98 44
56 80 46
57 63 25
57 85 22
57 91 60
57 92 75
58 62 6
58 69 82
58 88 34
59 63 36
59 74 59
59 93 51
59 95 10
60 61 91
60 68 24
60 87 5
60 95 33
61 67 65
61 77 22
61 78 42
61 81 96
61 95 84
62 64 14
62 75 32
62 89 1
62 99 44
63 81 41
63 87 42
64 78 98
65 71 74
66 68 65
66 81 22
66 90 13
67 81 25
67 82 29
67 90 5
67 98 37
68 91 21
68 100 36
69 89 69
70 73 33
70 85 74
70 96 83
71 85 76
71 94 97
71 95 41
72 81 95
72 83 62
73 98 78
75 87 55
75 93 17
75 97 52
76 94 18
76 96 1
77 80 74
77 83 35
77 92 12
77 99 73
78 84 54
78 86 75
78 91 73
80 93 55
81 89 41
81 100 37
82 96 91
85 97 88
86 90 98
88 94 48
91 97 28
91 99 9
93 94 70
94 95 13
0 0