黑板上有一個正整數 N，然後球主跟夢月輪流將黑板上的數字擦掉，並在黑板上寫一個被擦掉數字的某個真因數(也就是小於 N 的正因數)。當某個人在黑板上寫下 "1" 的時候，遊戲就結束了。對於球主來說，在黑板上寫下數字 d，可以得到 P[d] 分；但是同樣的數字如果是夢月來寫，夢月會得到 Q[d] 分。
假設兩人皆是絕頂聰明的情形下，彼此都希望能夠極大化自己的分數減去對手的分數。請你幫忙算算，若是球主先開始，或是夢月先開始，最終與對手的得分差距是多少呢？
輸入的第一行有一個整數 T 表示有幾組測資(本題的 T 超大，T>=500000)。
每一組測試資料的第一行有四個正整數 n1, n2, n3, D (1<=n1, n2, n3<=5*106; 1<=n1*n2*n3<=8*1018)，於是 N = n1*n2*n3，D 為 N 的正因數個數。接下來有 D-1 行，每一行有兩個整數，對應到由小到大所有真因數的得分 P[d] 以及 Qd。
輸入保證每一筆測試資料的 D 不會超過 106，而且，所有測試資料的 D 加起來不會超過 5*107。
對於每一筆測試資料，請輸出兩個數字，分別代表球主先開始，和夢月先開始的話最終與對手的最佳得分差距。
2 7 1 1 2 2 1 2 2 1 3 1 3 6 6
2 1 3 5
Migrated from old NTUJ.
poi
| No. | Testdata Range | Score |
|---|