2
1000
1 2
1 2
5 3
3 1
3 1
4 1
3 1
1 2
3 1
3 4
1 2
3 4
1 2
5 3
1 2
3 1
5 3
3 1
4 1
3 1
4 1
5 3
4 1
3 1
1 2
3 1
3 4
3 1
5 3
3 1
3 4
1 2
5 3
3 1
4 1
5 3
3 4
5 3
5 3
1 2
1 2
1 2
3 4
1 2
3 4
1 2
4 1
4 1
4 1
4 1
3 4
3 1
4 1
3 4
5 3
4 1
5 3
3 1
4 1
3 1
1 2
4 1
3 4
5 3
3 4
3 4
5 3
4 1
3 1
1 2
4 1
5 3
4 1
4 1
1 2
1 2
5 3
4 1
3 4
5 3
4 1
3 1
1 2
4 1
3 1
5 3
1 2
3 1
3 4
5 3
1 2
1 2
3 1
1 2
3 4
3 4
3 1
1 2
4 1
4 1
4 1
1 2
1 2
1 2
1 2
4 1
5 3
3 1
4 1
3 4
4 1
3 4
3 1
5 3
5 3
1 2
1 2
1 2
1 2
1 2
4 1
3 1
3 4
3 1
3 1
5 3
3 1
3 1
4 1
4 1
5 3
3 1
3 4
3 1
4 1
4 1
3 4
4 1
3 4
3 4
3 4
5 3
4 1
1 2
3 4
3 4
1 2
1 2
3 4
4 1
1 2
5 3
5 3
4 1
5 3
3 1
4 1
4 1
3 4
4 1
1 2
3 1
5 3
3 1
1 2
5 3
3 1
1 2
1 2
5 3
3 4
4 1
1 2
4 1
1 2
3 1
5 3
3 4
3 1
3 4
5 3
3 1
3 1
3 4
1 2
5 3
4 1
1 2
5 3
3 4
1 2
5 3
3 4
3 1
5 3
3 4
1 2
4 1
5 3
3 4
3 1
3 4
3 1
1 2
4 1
5 3
4 1
4 1
3 4
1 2
4 1
1 2
3 1
5 3
4 1
3 4
5 3
1 2
1 2
1 2
1 2
3 1
3 1
3 1
1 2
3 4
3 4
3 4
4 1
5 3
3 4
3 1
3 1
3 4
5 3
4 1
3 1
4 1
3 4
5 3
3 1
3 1
4 1
4 1
3 4
3 1
4 1
5 3
4 1
5 3
1 2
4 1
3 1
3 1
4 1
3 4
5 3
1 2
1 2
3 1
5 3
3 1
5 3
4 1
5 3
3 1
3 1
5 3
1 2
3 1
1 2
3 4
3 4
1 2
1 2
4 1
3 1
3 1
3 4
3 1
1 2
3 1
1 2
4 1
3 1
4 1
4 1
3 4
5 3
1 2
3 1
5 3
4 1
1 2
1 2
1 2
3 4
3 4
1 2
1 2
3 4
4 1
3 4
3 1
5 3
1 2
3 4
1 2
3 1
4 1
3 1
5 3
3 4
3 4
1 2
5 3
1 2
1 2
1 2
1 2
5 3
5 3
1 2
3 1
4 1
5 3
3 4
1 2
3 4
5 3
5 3
3 4
4 1
5 3
4 1
4 1
5 3
5 3
4 1
4 1
1 2
3 1
3 1
1 2
4 1
3 1
5 3
5 3
1 2
5 3
5 3
3 4
4 1
3 1
3 4
4 1
4 1
3 1
4 1
3 4
5 3
1 2
5 3
1 2
4 1
3 1
3 4
4 1
5 3
4 1
5 3
3 4
3 4
5 3
3 1
1 2
3 4
4 1
4 1
1 2
4 1
5 3
3 4
1 2
4 1
1 2
5 3
4 1
5 3
3 4
1 2
3 1
3 4
5 3
1 2
3 4
5 3
5 3
5 3
4 1
5 3
3 1
1 2
4 1
5 3
1 2
1 2
5 3
3 4
3 4
3 4
1 2
4 1
5 3
1 2
3 4
4 1
3 1
3 4
3 4
3 4
4 1
4 1
3 1
1 2
4 1
3 1
1 2
3 4
3 1
1 2
4 1
5 3
3 1
3 1
3 4
5 3
4 1
3 4
1 2
5 3
3 1
1 2
3 1
5 3
5 3
3 4
3 1
3 4
3 1
4 1
3 4
4 1
4 1
5 3
3 4
3 4
4 1
3 1
3 1
3 4
4 1
4 1
1 2
5 3
1 2
3 1
5 3
3 4
3 4
5 3
4 1
3 4
3 4
1 2
5 3
3 4
1 2
3 1
4 1
5 3
3 4
1 2
3 4
1 2
3 1
4 1
5 3
5 3
1 2
1 2
4 1
3 1
3 1
3 1
1 2
5 3
4 1
1 2
4 1
1 2
4 1
3 4
4 1
1 2
5 3
5 3
4 1
3 4
4 1
4 1
1 2
3 1
5 3
3 4
5 3
4 1
3 1
3 4
1 2
3 1
3 1
3 4
3 4
5 3
4 1
4 1
5 3
3 1
1 2
3 4
3 1
5 3
3 1
3 1
1 2
3 4
3 4
3 4
3 1
1 2
3 4
5 3
3 4
3 4
3 1
3 1
4 1
5 3
4 1
3 4
3 4
5 3
3 1
1 2
5 3
3 4
5 3
3 1
5 3
1 2
3 4
1 2
5 3
3 1
4 1
5 3
5 3
3 1
4 1
3 1
5 3
1 2
3 1
3 4
1 2
5 3
1 2
1 2
1 2
1 2
4 1
3 1
5 3
1 2
4 1
3 4
3 4
3 4
1 2
5 3
3 1
5 3
3 1
4 1
5 3
3 4
3 4
3 1
4 1
3 1
3 4
3 4
5 3
3 1
3 4
4 1
3 4
1 2
3 1
3 4
3 4
3 1
3 4
1 2
1 2
5 3
3 4
3 4
5 3
5 3
3 4
3 4
3 1
5 3
3 4
3 1
4 1
5 3
3 1
4 1
1 2
3 4
5 3
5 3
3 1
5 3
4 1
4 1
3 1
5 3
3 1
3 4
3 1
5 3
4 1
1 2
3 4
3 1
3 4
3 4
3 1
3 4
4 1
3 1
3 4
4 1
4 1
1 2
5 3
3 4
4 1
3 4
3 4
3 4
4 1
5 3
3 4
4 1
5 3
3 4
1 2
5 3
1 2
4 1
5 3
3 1
4 1
5 3
4 1
1 2
1 2
3 1
5 3
3 1
5 3
3 4
5 3
4 1
3 1
1 2
1 2
4 1
4 1
3 4
3 4
4 1
5 3
3 1
1 2
1 2
5 3
1 2
3 1
1 2
3 4
3 4
1 2
3 1
3 1
3 1
1 2
3 1
5 3
3 1
3 1
3 4
1 2
3 1
3 1
1 2
4 1
3 4
1 2
4 1
3 4
3 4
4 1
1 2
1 2
3 1
3 4
5 3
4 1
3 1
5 3
3 4
3 4
1 2
4 1
4 1
3 4
3 1
3 4
3 1
1 2
5 3
3 4
5 3
1 2
4 1
4 1
5 3
3 1
5 3
5 3
5 3
1 2
3 1
3 4
4 1
4 1
3 4
3 1
1 2
5 3
3 4
1 2
5 3
4 1
3 4
1 2
3 4
1 2
4 1
1 2
1 2
1 2
3 1
4 1
3 4
3 4
3 1
4 1
3 4
1 2
4 1
5 3
3 1
5 3
3 4
4 1
5 3
3 4
1 2
4 1
1 2
3 4
4 1
5 3
4 1
4 1
3 1
4 1
5 3
3 1
3 1
1 2
3 1
1 2
3 1
5 3
1 2
1 2
5 3
3 1
1 2
3 1
3 4
5 3
3 4
1 2
1 2
4 1
3 1
3 1
3 4
5 3
5 3
1 2
4 1
4 1
4 1
1 2
3 1
3 1
5 3
3 4
3 1
3 1
1 2
5 3
5 3
1 2
1 2
3 4
3 1
4 1
3 4
3 4
3 4
4 1
1 2
4 1
3 1
1 2
5 3
5 3
1 2
3 1
5 3
4 1
1 2
3 4
3 4
3 4
4 1
5 3
3 4
5 3
3 4
1 2
5 3
3 4
3 1
5 3
5 3
3 4
4 1
3 1
1 2
1 2
5 3
3 4
5 3
3 1
3 4
4 1
3 4
1 2
1 2
4 1
1 2
5 3
3 1
3 4
1 2
4 1
4 1
5 3
5 3
3 1
1 2
3 1
1 2
5 3
5 3
5 3
1 2
3 4
3 1
4 1
3 4
3 1
3 1
4 1
1 2
4 1
5 3
1 2
3 1
5 3
3 4
3 4
4 1
1 2
4 1
5 3
3 1
1 2
5 3
5 3
1 2
3 1
5 3
3 1
5 3
4 1
5 3
1 2
1 2
3 1
4 1
3 1
3 4
1 2
4 1
1 2
4 1
5 3
4 1
4 1
3 4
3 1
4 1
3 4
3 1
3 1
3 1
1 2
3 1
4 1
3 4
3 4
1 2
4 1
3 4
3 1
3 1
3 4
3 1
3 4
5 3
3 4
4 1
3 1
3 4
4 1
3 1
3 4
4 1
3 1
3 4
3 4
3 4
1 2
3 4
4 1
4 1
3 1
3 4
5 3
4 1
5 3
3 4
1 2
5 3
3 4
3 4
3 4
15
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
