題目描述

 給定n,m,p，求

的值

輸入格式

 

第一行：兩個整數Q, P

接下來Q行：輸入兩個整數Ni,Mi

（1<=q<=5000, 1<=P<=10^6）

（1<=Ni<=2^32-1 1<=Mi<=10^7）

保證Ni為素數并且Ni, P互質

輸出格式

 Q行

的值（對於每個Mi Ni)

Samples

4 16
7 1
3 3
5 9
17 10000

7
11
5
1

提示

 看什麽，這種題還要提示？

備註

抄襲=dead

原始資料

• Zero1 題號：b186
• Hydro 題號：Z1186
• Locale：zh_CN
• Display：open