Background

其他的屑学长要求小P把题面融入游戏元素，于是小C就来帮忙了。小C是一名忠实的yo-gi-oh玩家，由于不太聪明只会玩源。

接下来是几张卡的内容

No.1 源数之门-壹

1星怪兽×3

①：这张卡不会被战斗破坏。

②：这张卡和对方怪兽进行战斗的伤害步骤结束时把这张卡1个超量素材取除才能发动。自己场上的全部「源数」怪兽的攻击力直到回合结束时变成2倍。

攻击力:1000 守备力:100

No.2 源数之门-贰

1星怪兽×3

①：这张卡不会被战斗破坏。

②：这张卡和对方怪兽进行战斗的伤害步骤结束时把这张卡1个超量素材取除才能发动。自己场上的全部「源数」怪兽的攻击力直到回合结束时变成2倍。

攻击力:1000 守备力:100

No.3 源数之门-叁

1星怪兽×3

①：这张卡不会被战斗破坏。

②：这张卡和对方怪兽进行战斗的伤害步骤结束时把这张卡1个超量素材取除才能发动。自己场上的全部「源数」怪兽的攻击力直到回合结束时变成2倍。

攻击力:1000 守备力:100

No.4 源数之门-肆

1星怪兽×3

①：这张卡不会被战斗破坏。

②：这张卡和对方怪兽进行战斗的伤害步骤结束时把这张卡1个超量素材取除才能发动。自己场上的全部「源数」怪兽的攻击力直到回合结束时变成2倍。

攻击力:1000 守备力:100

源数网络

这个卡名的①的效果1回合只能使用1次。

①：自己主要阶段，把满足发动条件的1张「源数」通常魔法卡从卡组送去墓地才能发动。这个效果变成和那张魔法卡发动时的效果相同。

②：只要这张卡在场地区域存在，自己场上的「源数」超量怪兽把超量素材取除来让效果发动的场合，也能不把超量素材取除来发动。

源数直系

①：自己的场地区域有「源数网络」存在，自己场上没有怪兽存在的场合才能发动。从额外卡组把最多4只「源数之门」超量怪兽特殊召唤（同名卡最多1张）。这个效果特殊召唤的怪兽在结束阶段除外。这个效果的发动后，直到回合结束时自己只能有1次把怪兽召唤·特殊召唤。

Description

小C已经厌倦了拍「源数网络」然后使用「源数直系」哐哐打对手的生活。于是小C选择了开挂。

于是小C的额外卡组拥有了无穷张的「No.1 源数之门-壹」「No.2 源数之门-贰」「No.3 源数之门-叁」「No.4 源数之门-肆」

「源数之门」的效果修改为了： ①：自己的场地区域有「源数网络」存在，自己场上没有怪兽存在的场合才能发动。从额外卡组把 $b$ 只「源数之门」超量怪兽特殊召唤。这个效果特殊召唤的怪兽在结束阶段除外。这个效果的发动后，直到回合结束时自己只能有1次把怪兽召唤·特殊召唤。

「No.1 源数之门-壹」「No.2 源数之门-贰」「No.3 源数之门-叁」「No.4 源数之门-肆」的初始攻击力变更为 $a$ 它们的效果也被修改

②：这张卡和对方怪兽进行战斗的伤害步骤结束时把这张卡1个超量素材取除才能发动。自己场上的全部「源数」怪兽的攻击力直到回合结束时变成 $a$ 倍。

然后小C就和别人进行了决斗，但小C非常惊恐地发现他必须算出最后一只怪兽进行攻击时它的攻击力模 $p$ 的值，要不然就会输掉决斗。此时小C想起来自己还在晚自习于是向隔壁的竞赛之后疯狂补作业的小P求助。

PS:①每个怪兽只能进行一次攻击

②小C学长一定会发动怪兽的②效果

Format

Input

第一行是一个整数$T$，表示一共有T次询问；

接下来一共$T$行，每行三个正整数，分别为题目中的$a,b,p$；

Output

一共$T$行，每行一个整数，为每次提问对应的攻击力

Samples

3
2 5 17
5 4 3
1 45 11

15
1
1

5
2 10 23
5 14 19
19 28 29
514  19 17
12345 54321 7

12
9
1
13
1

Limitation

保证$a$，$p$互质并且$p$为质数

对于$30\%$的数据，保证 $0<T\le5 \times 10^5$，$0<a\le5 \times 10^6$，$0<b\le10^{18}$，$0<p\le10^7+10$。

对于$50\%$的数据，保证 $0<T\le5 \times 10^5$，$0<a\le5 \times 10^6$，$0<b\le10^{30}$，$0<p\le10^7+10$。

对于$100\%$的数据，保证 $0<T\le5 \times 10^5$，$0<a\le5 \times 10^6$，$0<b\le10^{100}$，$0<p\le10^7+10$。