Counting LCM Arrays

Given two integers n and k, your task is to count the number of arrays a_1, a_2,\dots, a_n of positive integers where \operatorname{lcm}(a_i, a_{i+1}) = k for all 1 \le i < n. Input The first line has an integer t: the number of test cases. The next t lines have two integers n and k: the length of the array and the value of lcm. Output Print t integers: the answer to each test case modulo 10^