input:

1000
7
3 6
4 3
5 3
2 6
1 4
7 1
12
5 7
10 7
2 10
11 2
1 7
8 1
4 2
9 11
6 9
12 11
3 5
6
2 5
1 2
4 5
6 4
3 6
5
2 5
1 5
4 5
3 2
8
1 8
2 8
4 2
6 1
5 6
7 6
3 8
8
3 8
7 3
4 8
6 4
2 7
5 2
1 4
4
3 1
4 3
2 1
6
5 1
6 1
2 5
3 5
4 2
12
8 11
5 11
12 8
3 12
6 12
2 3
4 6
10 11
1 5
9 5
7 5
9
6 1
7 6
4 7
8 7
5 4
9 6
...

output:

948445317
468414020
550143557
918384806
711758412
487662742
776412276
869581749
362768784
765628773
448285661
887328316
498957180
830953635
760637552
908032643
886182489
235413636
639862309
221832080
433351719
190990630
488338674
406692145
698771049
406557702
265705536
734677287
856271824
778877077
...

result:

wrong answer 9th lines differ - expected: '240852807', found: '362768784'