题目描述

在新格尔软件公司有两个无聊的程序员，牛喜文和菜怒武每天都喜欢研究一些无聊的方式打发时间。今天他们找到了新的方式。两个人各选一个数字 $A$ 和 $B$，然后计算 $A$ 的 $B$ 次方的最后 $13$ 位是什么。

但是今天他们计算的结果并不一样，所以他们想知道正确答案是什么，这就需要你来帮帮他们啦！

输入格式

题目包含多组数据。

输入的第一行有一个整数 $T$（$1 \leq T \leq 100$），代表有 $T$ 组数据。

对于每组数据包含一行：

第一行有两个整数 $A$ 和 $B$（其中 $1 \leq A, B \leq 1000$）。

输出格式

对于每组数据，输出的第一行为 Case #x:，其中 $x$ 是数据编号（从 $1$ 开始）。

第二行一个整数，$A$ 的 $B$ 次方的最后 $13$ 位，如果不足 $13$ 位在前部补上 $0$。

样例输入

2
1 1
13 13

样例输出

Case #1:
0000000000001
Case #2:
2875106592253