在这个特殊的时期，很多同学小时候在家上课的梦想得以实现。宅家刷网课时代已开启，请于下方补交电信费用。

Ivyhole 有一家电信公司，他的老顾客 StarrySky 为了能更加顺利的看网课，想要升级一下家中的宽带。由于 StarrySky 囊中羞涩，而作为其私下好友 Ivyhole 也深知这一点，所以 Ivyhole 决定以“回馈老顾客”的活动帮助 StarrySky 解决难题。

很快，Ivyhole 的提议得到了公司领导的认可，但是，想要参加此活动的老顾客必须答对一道问题，否则，你将与本次活动无缘。具体问题如下：

该电信公司有 n 条恰好连成一行的网络线路需要维修，每条线路有 m 种维修规格可以选择，由于 Ivyhole 开发的新技术，只要这 n 条线路中有任意两条相邻线路所使用的维修规格相同，则可以起到加强信号传输速率的功效。换句话说，假设数组 a 表示为 n 条网络线路各自所选择的维修规格，则满足： 的维修方案就能起到加强信号传输速率的功效。

现在，需要 StarrySky 回答出一共有多少种能够起到加强信号传输速率功效的维修方案，由于答案可能很大，同时，直接对 p 取模十分常见，故此题需要对 取模。

本题为多组输入输出。

第一行输入一个正整数 ，表示测试数据的组数。

对于每组测试数据，输入三个正整数 ，表示有 n 条网络线路，每条线路有 m 种维修规格的选择，将答案对  取模。

对于每组测试数据输出一行一个非负整数，表示能起到加强信号传输速率功效的维修方案的数量对  取模的结果。

1
3 2 3

6

假设这两种维修规格分别用  表示，则所有可能的 6 种满足要求的维修方案为：(000)(001)(011)(100)(110)(111).