背景

小岛哥哥：“做出来这一题，我送你花裙子好不好呀？”
少女夜夜：“好呀好呀！”

描述

我们知道数字0～9可以用火柴棒表示出来。而减号可以用一根火柴棒表示出来，等于号可以用两根火柴棒表示出来。
现在给定N根火柴棒，有多少合法的"A-B=C"可以用恰好N根火柴棒摆出来呢？

这里，A,B,C都要求是正整数，且不允许有前导零，但是它们可以是一位数字，两位数字，三位数字，或者更多位数字。同时A,B,C的位数可以不一样。

格式

输入格式

输入有多组询问。第一行输入一个整数T，表示询问次数。
之后T行，每一行有两个整数N和M。

输出格式

对于每一组数据，以"Case #i: ans"的形式输出答案，其中答案为用N根火柴棒可以摆出来的合法"A-B=C"的个数，答案对M取余。

样例1

样例输入1

4
12 1000000007
17 1000000007
20 1000000007
147 1000000007

样例输出1

Case #1: 1
Case #2: 5
Case #3: 38
Case #4: 815630825

限制

对于20％的数据，1<=T<=10，5<=N<=24。
对于80％的数据，1<=T<=30，5<=N<=500。
对于100％的数据，1<=T<=1000，5<=N<=500，3<=M<=2000000000。

每一个测试点时限3秒。