那个人也许永远不回来了，也许明天回来~~~
小雅米为封印Fun魔王，封印了自己的元神，只留得ddc一人在世间独活。ddc集千年神力，换得小雅米回来的信息。信息包含三个数 l,r,kl, r, kl,r,k。设 xxx 代表小雅米将在 xxx 年后回归，x=∑ik(l≤i并且i≤r)x = \sum i ^ k (l \leq i 并且 i \leq r)x=∑ik(l≤i并且i≤r)，现在ddc想请问你，他心爱的小雅米到底多少年后才能回来。
第一行输入一个整数 TTT，表示数组组数(1≤T≤10)(1\leq T \leq 10)(1≤T≤10)。
接下来T行，每行输入三个数 l,r,k(1≤l,r≤1050000，1≤k≤5)l, r, k(1 \leq l,r \leq 10^{50000}，1 \leq k \leq 5)l,r,k(1≤l,r≤1050000，1≤k≤5)。
对于每一组询问输出一个 xxx，表示答案。
2 1 10 1 1 10 2
55 385
