Pika and Dukkar are roomie. Pika is a nerd and likes to play with mathematics! Pika's favourite topic is pascal triangle and he proclaims that he can solve any problem related to this. So Dukkar decides if it's really true!

Dukkar gives a number N and a prime number P. N is the Nth row of pascal triangle starting with 0. Dukkar asks Pika to find how many numbers in nth row are divisible by P. Since the number can be very large so, Pika has to write a program. Since end sem are coming and Pika has to top in his batch so he asks you for help. Can you help Pika?

Input

The first line of the test file will contain T (T < 100000) where T is the no. of test cases. Each of the next T lines will contain two integers N (0 <= N <= 10¹⁸)  and P (2 <= P <= 10⁵) as defined above.

Output

For each test case print on each line K the number of numbers divisible by P on Nth row of the pascal triangle.

Example

Input:
2
2 2
7 7
Output:
1
6