Dados dos enteros ~n~ y ~k~, tu tarea consiste en contar el número de arreglos ~a_1, a_2, ..., a_n~ de enteros positivos donde el mínimo común múltiplo ~\operatorname{lcm}(a_i, a_{i+1}) = k~ para todo ~1 \leq i < n~.

Entrada

La primera línea contiene un entero ~t~: el número de casos de prueba. Las siguientes ~t~ líneas contienen dos enteros ~n~ y ~k~: la longitud del arreglo y el valor del mínimo común múltiplo.

Salida

Imprime ~t~ enteros: la respuesta a cada caso de prueba módulo ~10^9 + 7~.

Restricciones

• ~1 \leq t \leq 1000~
• ~2 \leq n \leq 10^9~
• ~1 \leq k \leq 10^9~

Ejemplo de Entrada

3
3 4
4 6
1337 42

Ejemplo de Salida

11
64
602746233

Explicación: Los arreglos para el primer caso de prueba son ~[1, 4, 1], [1, 4, 2], [1, 4, 4], [2, 4, 1], [2, 4, 2], [2, 4, 4], [4, 1, 4], [4, 2, 4], [4, 4, 1], [4, 4, 2]~ y ~[4, 4, 4]~.