Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2116
Christopher's Christmas Letter

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Dashing thro' the snow,
In a one-horse open sleigh,
O'er the fields we go,
Laughing all the way;
Bells on bobtail ring,
Making spirits bright;
What fun it is to ride and sing
A sleighing song tonight!
Jingle, bells! Jingle, bells!
Jingle all the way!
Oh! What fun it is to ride in a one-horse open sleigh!

The Christmas Eve last year becomes a story that filled Christopher's hearts with joy. With your help on "Souvenirs of Love" problem, Christopher has already been out of danger. (If you're interested in the background, please see Christopher's Key Ring)

This time, Christopher received a letter from Father Christmas. It was sent on Christmas Eve, but coz the mailing jam, it was just received. To his surprise, Father Christmas didn't fall asleep as well as Christopher (but different reason ;). What is Santa Claus's trouble? Let's see, it's a math problem:

There're N different XX toys, to be sent to city X. Each time Santa Claus will send M (0 <= M <= N) toys to a single person as presents. The number of ways for fixed M is well-known I think. It is very strange that the people in city X hate such number M for a fixed N, if and only if the number of ways for it is multiple of a fixed prime P.

Santa Claus wonders how many Ms will be satisfying (not be hated by people in city X).

Input

The first line of the input contains one integer X (1 <= X <= 500), which is the number of test cases.

Next X lines each contains two integers N (1 <= N <= 10^100) and P (a prime, 2 <= P <= 10^7).

Output

You should write exactly X lines to the output. Each line contains the total number of satisfying Ms for that test case.

Sample Input

2
6 7
6 2

Sample Output

0
3

Author: XIN, Tao
Source: Online Contest of Christopher's Adventure
Submit    Status