说明

给出q、n、p，满足如下关系，求s。

$ s=(\sum_{i=1}^n q^i )\ mod \ p $

输入格式

第一行为t，意为t组数据。

接下来t行，每行依次给出q、n、p满足如下条件。

$1 \leq t \leq 100$

$1 \leq q,n,p \leq 10^9$

输出格式

依次输出结果s。

样例

2
2 3 100
511 4 520

14
184