第一行一个数字 TTT ，表示数据的组数。

接下来每行四个整数，表示 kkk，aaa，nnn，ddd 。

每行一个整数，表示答案 。

样例输入

5
5 7 5 7
6 8 6 8
70 35 26 72
90 18 32 64
123 321 123 321

样例输出

150448172
1121208122
276955429
1024718000
585044920

对于 100% 100\% 100% 的数据，k≤123,a,n,d<p=123456791 k \leq 123, a,n,d< p = 123456791k≤123,a,n,d<p=123456791。