Count of paths

Given a sequence of N integers: arr₀, arr₁, arr₂, ….. arr_N-1 and an integer K

K is divisible by all the array elements, ie: K % arr_i = 0 for (0 <= i <= N-1).

A directed graph is built using this sequence. A directed edge from the j^th to the i^th array element exists if j < i and a_i is divisible by a_j, ie: a_i % a_j = 0.

Find the count of different paths from 0^th element to i^th element for 0 <= i <= N-1. As the answer can be very large, return answer modulo 10⁹+7.

Input Format:

The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow. 

The first line contains two integers, 'N' and 'K', where N represents the sequence length.

The next line contains N integers, 'ai' for (0 <= i <= N-1).

Output Format:

Print N integers, where ith element denotes the count of different paths from 1st element to ith element.

Output for each test case will be printed in a separate line,

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4    
1 <= K <= 10^9  
1 <= ai <= 10^5

Time limit: 1 sec