J-昨天看见个题_2025年夏第九届河北工业大学程序设计校赛

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

前几天，lhw跟流云天说"昨天看见个题"。他把简要题意发过来之后，流云天发现跟某省赛的某一个题长得很像，而且赛时还没做出来。现如今，又一道相似的问题摆在流云天面前，流云天辗转反侧、夜不能寐。他实在是想不出来了，于是把这个问题给你写在了一张纸条上面： $\left\lfloor \dfrac{a}{b} \right\rfloor$ 。请你帮流云天求出这个式子的值。

其中 $a$ 用分解质因数的形式来表达， $a=p_{1}^{k_1}p_{2}^{k_2}p_{3}^{k_3} \cdots$ ，其中 $p_i$ 均为质数。由于这个式子的值实在太大，请输出这个数模 $P$ 的值，即 $\left\lfloor\dfrac{a}{b}\right\rfloor\bmod P$ 的值。

输入描述:

本题的单个测试点内含有多组测试数据。记  为测试点内测试数据组数：

在每组数据中，第  行输入三个正整数  。

接下来第  行到第  行，每行输入两个正整数  。

输出描述:

每行输出一个整数，代表你的答案。

示例1

输入

复制

1
1 2 11
5 2

输出

复制

备注:

【数据规模与限制】

保证单个测试点内所有  之和不超过 
保证所有  均为质数
保证  互质