题目描述

Brute 教授并不是很擅长算法设计。他手头现在有个代码：

现在他只知道 funny 这个操作会被调用太多次（Find 的参数表的第二个参数是一个函数），但是他懒得去算具体次数，并反手把活丢给了你。

输入格式

第一行为一个整数 $T(\le 100)$，即数据组数。

往后每一行为四个整数 $a,b,P,n(1\le a,b,P\le 10^6,1\le n\le 10^9)$。

$a,b,n$ 含义如代码所示。

提示：在 $a,b,P$ 固定的情况下，计算运算次数关于 $n$ 的递推式。

输出格式

每一行为对应数据的答案，由于答案可能很大，你需要输出对 $P$ 取模的结果。具体输出内容参考样例。

3
3 4 10 3
4 5 13 5
3 2 19 100

Case #1: 2
Case #2: 11
Case #3: 12