很久很久以前，Tyrone 国王有 $N$ 位大臣，我清楚地记得他们的薪水。我也知道，每当某位大臣的薪水低于他下方（即排名更靠后）的大臣的薪水时，就会有人抱怨，并有一位大臣被解雇；被解雇的大臣可以是任意一位，无论该大臣是否与抱怨有关。解雇会持续进行，直到没有人抱怨为止，即所有大臣的薪水呈非递增序列。此时，解雇停止。但我记不清大臣们被解雇的顺序了。

你能帮我整理一下这个故事吗？或者至少告诉我，我可能讲述了多少种不同的故事。如果两个故事中被解雇的大臣序列不同，则视为两个不同的故事。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行：第一行包含一个整数 $N$，第二行包含 $N$ 个用空格分隔的整数，表示从第一位到第 $N$ 位大臣的薪水。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是我可能讲述的故事数量，对 $10007$ 取模。

数据范围

内存限制：1GB。 每位大臣的薪水均为正整数且不超过 $10000$。

小型数据集（测试集 1 - 可见） 时间限制：60 秒。 $1 \le T \le 100$。 $1 \le N \le 100$。

大型数据集（测试集 2 - 隐藏） 时间限制：120 秒。 $1 \le T \le 20$。 对于 80% 的测试用例，$1 \le N \le 2000$。 对于所有测试用例，$1 \le N \le 8000$。

样例

样例输入 1

3
4
7 4 6 6
8
90 80 70 60 50 50 40 30
2
7 8

样例输出 1

Case #1: 14
Case #2: 1
Case #3: 2