#4407. 于神之怒加强版

题目描述

给下N,M,K.求

输入格式

输入有多组数据，输入数据的第一行两个正整数T,K，代表有T组数据，K的意义如上所示，下面第二行到第T+1行，每行为两个正整数N,M，其意义如上式所示。

输出格式

如题

样例

样例输入

1 2  

3 3 

样例输出

20  

数据范围与提示

1<=N,M,K<=5000000,1<=T<=2000

题解：JudgeOnline/upload/201603/4407.rar