Alice和Bob是一对好朋友，他们经常一起做游戏玩，游戏难度从小学数学到人类智慧都有涉及。 不过毕竟游戏虽然好玩，但是玩太多的话对学习还是有一定的负面影响的，Alice和Bob长期沉迷做游戏，导致数学测试不合格，无奈，他们只能参加补考。 补考模拟题是这样的，求

$∑_{i=1}^{n} ia^{i}$

Alice看了看题，表示这道题并不有趣，并撕掉了卷子，Bob拿到题之后也觉得这道题并不有趣，但是Bob希望补考通过，于是找你求助。 Bob认为补考时候题目也会和这个差不多，于是他决定训练自己的做题能力，他一次性生成了 T 个类似的题目，希望你能做出来他好比对答案。 Bob已经发现了如果把答案写出来的话整张试卷都写不完，因此他觉得试卷上肯定漏了点什么，Bob表示你只需要回答答案对 p 取模的结果就可以了。 注意：Bob为了让事情变得有趣些，每个题目的 p 不一定相同。

---

【输入格式】

输入共 T+1 行。

第一行一个正整数 T。

接下来 T 行每行三个正整数 n,a,p。

---

【输出格式】

输出共 T 行，每行一个整数，表示答案。

---

input

10

928 263217362 918273612

817 18276362 728192763

827162521 1 726152738

716253712 1 91827321

928172 263217362 918273612

192817 263217362 918273612

817263521 281738291 998244353

718293812 847266517 928172831

281726351 829102834 991827392

928172632 192832816 882716286

---

output

28467122

151221515

514235435

62627836

324294238

314165582

594969293

686205775

535702898

163391752