Input 
3
2 3 5
4
1 3
3 3
2 3
2 3
Output 
6
2
15
30