TEST DATA FOR `disease'

A Zip file of this data is available.

Input for test 1

6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1

Output for test 1

5

Input for test 2

5 5 1
2 1 2
2 1 3
2 1 4
2 1 5
2 2 3

Output for test 2

0

Input for test 3

5 5 5
2 1 2
2 1 3
2 1 4
2 1 5
2 2 3

Output for test 3

5

Input for test 4

10 5 3
2 2 3
1 3
2 3 4
3 1 2 4
2 2 3
3 2 3 5
3 1 4 5
4 1 3 4 5
3 1 3 5
3 1 3 5

Output for test 4

4

Input for test 5

100 7 4
1 3
3 3 4 7
0
1 7
2 2 7
0
3 1 5 6
0
1 5
2 3 4
1 3
3 2 3 6
1 5
1 2
3 3 4 6
1 1
3 2 4 7
2 1 2
2 1 2
2 4 5
1 4
2 2 7
1 6
2 1 2
3 2 5 6
0
2 4 6
0
1 4
1 2
0
2 2 4
1 3
2 5 6
2 3 6
1 4
1 7
2 2 3
3 1 2 7
0
1 5
2 1 4
1 2
1 6
3 3 5 6
0
2 4 5
3 2 5 6
3 3 5 6
1 7
1 5
2 2 6
1 4
3 3 4 5
1 4
0
1 3
2 3 7
3 1 5 7
1 3
2 6 7
1 6
0
2 1 6
0
2 3 4
0
1 4
1 1
1 4
1 1
2 1 3
1 5
1 5
1 1
1 2
2 3 6
1 2
1 3
2 1 2
1 7
1 1
3 1 2 6
3 1 5 7
0
1 7
1 3
1 3
0
2 3 6
0
0
0
0
2 5 7
3 1 5 7
2 2 4
2 1 4
2 3 7
1 2

Output for test 5

56

Input for test 6

100 9 5
2 2 7
0
3 1 3 9
0
1 3
1 9
1 8
3 2 5 9
2 2 8
3 1 2 4
2 2 6
2 5 6
3 5 6 9
2 3 8
1 3
1 1
2 6 7
1 1
4 1 2 8 9
2 3 8
1 9
0
2 1 3
0
1 2
0
3 1 5 7
0
2 2 7
3 4 5 6
2 1 7
4 2 3 4 7
2 3 6
3 3 4 6
3 5 6 7
0
1 7
4 2 6 7 9
2 3 6
2 2 5
1 2
0
1 8
2 3 6
1 2
2 1 9
3 1 2 6
1 7
3 2 4 7
0
0
1 9
0
1 1
3 3 6 7
2 4 7
3 4 5 6
2 1 7
3 2 8 9
3 4 5 7
2 2 7
1 5
3 5 7 8
1 2
1 5
3 4 6 9
4 2 3 7 8
2 2 4
3 1 2 4
2 6 9
4 1 3 7 9
3 1 7 9
1 5
2 3 6
2 1 6
2 6 7
0
1 5
2 1 2
2 1 7
2 2 6
2 5 7
3 4 5 9
3 1 2 6
2 5 7
3 6 8 9
0
1 2
1 6
3 2 4 9
0
0
3 1 4 5
0
0
5 3 4 5 7 9
2 3 5
1 4
3 1 3 5
1 7

Output for test 6

53

Input for test 7

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

Output for test 7

623

Input for test 8

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

Output for test 8

578

Input for test 9

1000 15 9
1 14
1 12
2 9 10
0
1 15
1 13
0
1 7
1 4
0
1 13
1 15
1 8
0
0
1 4
0
0
3 3 5 11
4 4 6 7 13
0
0
1 3
0
2 4 5
2 1 8
3 5 11 15
0
0
1 8
0
0
2 11 15
3 1 2 7
4 2 5 9 10
0
0
1 6
1 5
1 4
1 13
2 7 12
2 5 14
0
0
1 12
0
1 7
1 14
2 8 10
1 1
1 2
1 12
1 15
2 1 7
0
0
1 6
0
1 4
2 8 10
1 2
1 5
3 1 10 12
1 4
0
1 3
2 7 9
0
1 3
2 2 13
0
2 3 8
0
0
1 1
1 13
1 8
1 13
1 1
1 8
1 2
1 10
1 9
1 10
1 6
1 2
0
1 12
0
3 4 5 10
2 11 14
2 2 6
1 5
0
1 11
0
3 4 7 11
0
1 3
2 1 12
0
2 5 15
1 5
2 7 12
0
1 15
2 6 10
4 3 7 13 15
3 12 13 15
0
0
1 14
0
1 7
0
1 8
0
0
1 15
1 9
1 3
0
1 5
2 3 11
1 6
1 5
3 5 6 12
0
4 2 5 13 14
0
1 1
1 3
1 2
2 10 13
0
1 3
1 6
1 12
1 8
1 15
2 13 14
2 1 10
1 15
1 11
0
1 10
0
0
0
0
2 11 12
1 15
0
3 5 10 15
0
1 1
1 13
2 10 12
0
0
1 4
3 3 10 13
0
1 14
2 5 15
1 1
0
0
2 5 14
0
1 6
1 13
2 13 14
1 7
1 7
0
0
0
1 7
1 9
0
0
1 1
3 2 10 12
2 4 10
0
0
3 1 3 15
0
0
1 1
0
1 3
0
2 7 12
2 3 12
1 10
0
1 11
1 6
0
0
1 3
1 14
0
1 13
0
0
1 12
1 15
1 9
0
0
0
0
0
1 9
1 2
1 4
1 4
0
0
1 7
1 13
0
1 2
3 1 2 13
1 13
0
1 14
0
2 12 15
1 11
2 1 12
0
2 7 9
1 13
2 6 7
1 13
0
1 15
1 14
2 9 15
1 12
0
0
0
2 12 13
0
2 7 10
1 3
4 6 12 13 14
1 11
0
1 4
0
0
1 4
2 1 7
0
0
3 1 5 7
1 12
3 1 13 14
1 12
0
1 8
1 4
1 15
2 7 15
1 11
4 2 3 4 15
1 13
0
0
0
1 10
0
1 9
2 2 9
1 12
0
1 15
1 5
1 5
2 5 14
1 9
0
0
0
1 3
1 8
1 10
0
0
2 5 7
1 1
0
3 1 8 15
0
1 11
0
1 14
1 11
1 2
1 10
0
2 7 15
0
1 11
2 8 15
2 2 3
4 1 11 12 15
1 2
1 6
2 8 15
1 13
0
0
1 1
3 3 9 15
2 5 14
1 1
2 2 11
1 10
3 1 6 7
2 8 13
0
0
1 7
3 5 13 14
1 5
2 4 5
1 2
0
0
1 4
2 10 11
1 5
0
3 3 5 10
1 12
1 2
1 6
1 4
3 5 8 14
0
1 11
2 10 15
1 1
0
1 2
3 1 7 13
0
0
0
1 1
0
1 10
1 4
0
1 1
1 1
0
0
1 5
4 2 4 5 15
2 2 15
1 10
1 10
0
1 8
1 11
1 9
1 10
2 1 4
0
0
1 11
3 5 10 15
1 9
5 1 9 11 12 13
0
1 15
0
1 6
2 6 13
0
1 12
4 1 9 12 13
1 10
1 9
1 7
2 6 14
0
1 5
1 7
2 11 13
0
1 8
1 9
0
0
1 6
1 8
1 11
0
3 1 12 15
1 14
0
0
1 10
1 10
0
1 2
1 2
0
1 9
0
0
0
0
1 6
1 3
0
3 1 2 9
1 2
0
1 1
2 5 6
2 12 14
1 14
2 8 15
1 5
0
1 15
1 15
2 6 10
1 15
0
0
1 9
2 7 9
2 3 9
1 2
2 2 8
2 4 6
0
1 13
0
2 3 4
0
2 12 13
2 10 11
1 7
1 15
0
1 1
1 7
0
0
0
0
1 4
2 14 15
2 4 12
1 2
1 8
2 3 6
2 3 5
1 4
1 1
1 2
0
3 5 10 13
0
1 7
1 6
1 9
2 3 13
1 9
1 7
0
1 5
3 7 13 14
0
2 4 9
0
1 1
2 2 6
0
1 11
0
0
2 1 13
0
1 11
1 13
1 5
0
1 1
0
0
0
1 15
1 10
0
1 1
2 2 11
2 5 8
0
0
1 10
1 7
0
2 2 7
1 12
1 13
1 10
0
0
0
2 4 8
0
1 8
1 3
1 9
0
0
2 13 15
0
2 11 14
1 10
3 4 9 15
1 2
2 1 9
1 1
0
1 14
2 3 12
0
0
2 4 10
3 1 11 12
1 5
2 5 8
0
1 10
0
2 11 13
3 3 6 9
0
1 4
1 12
1 15
1 5
0
0
2 10 14
2 11 13
1 9
0
1 9
0
1 15
1 4
1 2
1 15
0
0
0
3 9 14 15
0
1 5
0
1 14
0
2 9 10
0
0
1 4
1 15
0
2 10 13
0
1 3
1 6
1 6
1 15
0
0
0
1 2
1 2
0
3 5 7 12
0
0
0
1 11
2 4 8
1 12
0
2 2 12
1 9
1 3
1 5
0
2 1 3
0
3 5 8 15
0
0
1 14
1 11
1 8
0
2 4 6
1 5
0
1 8
0
1 5
2 11 14
0
2 7 14
1 1
2 4 11
2 7 13
0
0
1 3
1 13
0
3 7 9 12
1 3
1 11
0
0
1 4
0
2 3 7
1 14
0
1 3
0
2 1 14
0
1 13
3 7 9 15
3 3 14 15
2 5 11
3 2 3 7
2 8 14
0
1 9
0
3 6 7 15
4 8 11 14 15
3 2 12 14
2 6 10
0
0
1 3
1 2
1 8
0
0
2 2 9
0
2 10 11
1 1
1 4
2 5 9
0
3 4 6 9
0
1 2
2 7 15
2 10 14
2 4 6
0
0
4 2 9 12 13
0
0
0
1 6
2 7 10
0
3 8 10 13
2 3 15
2 1 6
1 13
1 12
3 3 12 13
0
5 2 10 11 12 15
1 5
2 2 10
1 14
0
0
1 11
0
0
0
2 9 12
0
2 3 7
1 6
0
2 13 14
1 1
1 13
0
0
1 11
0
0
1 7
0
0
4 1 2 7 12
0
2 6 8
0
0
1 14
0
1 8
0
0
1 14
1 2
3 2 3 12
0
0
2 1 12
1 5
0
2 2 14
0
1 6
1 3
2 6 12
0
0
2 7 11
0
3 2 3 4
2 1 9
0
0
1 15
1 2
0
2 4 15
0
1 2
2 2 12
2 6 10
2 3 11
1 6
2 3 4
2 11 13
2 1 4
1 13
3 4 5 7
1 4
2 9 14
2 11 15
1 14
2 9 14
1 4
0
2 2 15
0
0
0
3 8 10 14
1 2
0
0
1 10
2 8 11
1 11
0
2 4 8
1 7
0
0
1 11
0
0
0
3 6 11 12
0
2 9 15
1 9
1 4
1 11
0
0
3 4 9 13
1 7
1 15
2 5 12
2 5 13
1 7
1 7
2 6 8
0
0
2 5 14
1 3
1 6
1 1
1 1
1 11
0
1 7
0
0
1 5
0
2 2 4
2 6 10
2 11 12
1 12
0
2 1 7
1 14
0
1 1
2 3 13
1 11
0
0
3 8 12 14
1 6
1 11
0
1 14
0
2 5 7
1 13
2 4 5
0
2 12 15
1 5
0
1 1
1 10
1 14
2 11 15
2 9 13
2 2 7
0
2 5 14
0
0
3 3 7 13
0
2 12 13
2 1 3
1 15
2 5 9
1 3
1 4
3 1 3 11
2 1 9
1 3
3 1 6 10
0
1 14
0
5 2 4 5 14 15
0
2 5 14
2 2 11
1 2
0
1 13
2 1 10
0
0
0
2 4 7
1 14
2 6 13
1 3
2 4 8
4 1 4 5 7
1 12
5 1 2 5 6 12
0
1 7
0
1 12
0
2 4 9
0
1 14
1 15
3 6 10 12
2 1 3
0
0
2 1 10
1 6
1 7
2 11 14
2 9 14
1 6
0
1 5
3 1 5 9
0
1 3
2 7 12
2 4 10
1 13
0
1 10
1 2
0
3 2 4 7
1 4
0
0
1 2
2 8 13
1 12
1 1
2 4 15
0
1 13
1 10
2 3 7
0
2 6 15
1 1
2 1 15
0
0
0
0
0
0
2 7 8
0
0
2 2 7
2 11 12
2 1 3
0
3 3 11 15
1 3
0
0
2 1 10
2 2 4
1 15
4 8 11 12 15
0
1 7
1 15
1 7
0
0
1 2
2 7 15
2 4 8
2 1 7
1 9
0
0
2 5 8
2 8 14
1 8
4 1 4 8 15
0
4 3 5 7 11
0
2 8 10
4 3 5 8 9
2 6 9
2 1 10
1 7
2 9 10
2 4 12
2 6 7
0
3 8 11 12
0
1 4
4 1 4 12 13
1 10

Output for test 9

685