Description

给定询问组数T和取模数R，每次询问给定两个整数n和m(m<=n)，求1~n!的数中与m!互质的数的个数。答案对R取模，R是质数。

Format

Input

第一行为两个整数T，R表示该组中测试数据数目，R为模数。
后面T行，每行一对整数n，m， m<=n。

Output

共T行，表示答案。

Sample 1

Input

1 11
4 2

Output

1

Limitation

1s, 512MB for each test case.
对于100%的数据，R<=10^9+10，T<=10000，1 < = N , M < = 10000000
数据有梯度。