5
2 2 2
8 1
4 6
1 4
2 2 2
1 1
9 9
1 2
4 1 2
2 1 8 6
999999999
1 9
7 9 5
7 11 9 1 2 18 11
8 13 4 10 1 13 2 10 16
8 9 3 13 12
5 4 1
857487028 773029872 845119807 475685071 988386263 
771098833 170131470 947400180 790206795
191652034