import java.util.*; import java.io.*; /* * @author -- rajatgoyal715 */ public class CuttingBoards { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); StringBuilder sb = new StringBuilder(""); while(t--!=0){ int m = sc.nextInt(); int n = sc.nextInt(); long y[] = new long[m-1]; for(int i=0;i=0&&j>=0){ if(y[i]>=x[j]){ cost += vertical*y[i]; i--; horizontal++; } else{ cost += horizontal*x[j]; j--; vertical++; } } while(j>=0){ cost += horizontal*x[j]; j--; vertical++; } while(i>=0){ cost += vertical*y[i]; i--; horizontal++; } return cost%mod; } }