There are N students in a class.The students of a class are to be divided into different groups for projects. Each group can have only 2 students. The class teacher comes up with a brilliant idea of making the groups according to roll numbers such that the prime factorization of roll number X and roll number Y have some factors in common. The product of the common factors of X and Y is M. A single roll number can be selected in multiple groups. A roll number can be selected with itself also meaning (X,X) is a valid group. A group (X,Y) is formed iff X>=Y. Help the teacher in estimating how many groups are formed.

 

Input

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two integers N and M as described above.

Output

• For each test case, output a single line containing the number of groups as described above.

Constraints

• 1 = T = 100
• 1 = N,M = 1000000

Example