seuOJ248 - ddc的千年等待

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：6000 ms
• 空间限制：512 MiB
• 题目标签：春季, 夏季, 校赛, 初赛, 2021

题目描述

那个人也许永远不回来了，也许明天回来~~~

小雅米为封印Fun魔王，封印了自己的元神，只留得ddc一人在世间独活。ddc集千年神力，换得小雅米回来的信息。信息包含三个数 $l, r, k$。设 $x$ 代表小雅米将在 $x$ 年后回归，$x = \sum i ^ k (l \leq i 并且 i \leq r)$，现在ddc想请问你，他心爱的小雅米到底多少年后才能回来。

输入格式

第一行输入一个整数 $T$，表示数组组数$(1\leq T \leq 10)$。

接下来T行，每行输入三个数 $l, r, k(1 \leq l,r \leq 10^{50000}，1 \leq k \leq 5)$。

输出格式

对于每一组询问输出一个 $x$，表示答案。

样例

样例输入

2
1 10 1
1 10 2

样例输出

55
385