题目描述

夜雷在新日暮里买了一块地来经营史莱姆农场，因为经费紧张，他的钱只够买一只史莱姆。

但是不用担心，史莱姆的繁殖能力非常强，每一天结束它都会分裂成 $a$ 个史莱姆，分裂的史莱姆还会再分裂。

同时夜雷的每个畜栏都有 $p$ 的容量，当畜栏满了，他就会把该畜栏的史莱姆卖掉。

夜雷想让你帮他算算，$b$ 天后他会拥有多少只史莱姆。

输入格式

输入一个 $t$，表示 $t$ 组样例。

每组样例一行三个整数，分别代表 $a,b,p$。

输出格式

一行一个整数，表示 $b$ 天后夜雷会拥有多少只史莱姆。

1
2 10 9

7

数据范围

$0 ≤a,b<2^{31} ,a + b > 0,2 ≤ p <2^{31}$