The binomial coefficient C(N, K) is defined as N! / K! / (N − K)! for 0 ≤ K ≤ N.
Here N! = 1 * 2 * ... * N for N ≥ 1, and 0! = 1.

You are given a prime number P and a positive integer N.

A_L is defined as the number of elements in the sequence C(N, K), such that, P^L divides C(N, K), but P^L+1 does not divide C(N, K). Here, 0 ≤ K ≤ N.

Let M be an integer, such that, A_M > 0, but A_L = 0 for all L > M. Your task is to find numbers A₀, A₁, ..., A_M.

Input Format
The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The only line of each test case contains two space-separated integers N and P.

Output Format
For each test case, display M + 1 space separated integers A₀, A₁, ..., A_M on the separate line.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 10¹⁸
2 ≤ P < 10¹⁸
P is prime

Sample Input

3
4 5
6 3
10 2

Sample Output

5
3 4
4 4 1 2

Explanation

Example case 1. Values C(4, K) are {1, 4, 6, 4, 1}. Each of them is not divisible by 5. Therefore, A₀ = 5, A₁ = 0, A₂ = 0, ..., hence the answer.

Example case 2. Values C(6, K) are {1, 6, 15, 20, 15, 6, 1}. Among them 1, 20, 1 are not divisible by 3, while remaining values 6, 15, 15, 6 are divisible by 3, but not divisible by 9. Therefore, A₀ = 3, A₁ = 4, A₂ = 0, A₃ = 0, ..., hence the answer.

Example case 3. Values C(10, K) are {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1}. Among them 1, 45, 45, 1 are not divisible by 2, values 10, 210, 210, 10 are divisible by 2, but not divisible by 4, value 252 is divisible by 4, but not divisible by 8, finally, values 120, 120 are divisible by 8, but not divisible by 16. Therefore, A₀ = 4, A₁ = 4, A₂ = 1, A₃ = 2, A₄ = 0, A₅ = 0, ..., hence the answer.