Christopher's Christmas Letter
Time Limit: 1 Second Memory Limit: 32768 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 3Submit
Source: Online Contest of Christopher's Adventure