All submissions for this problem are available.
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.
- 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.
- For each test case, output a single line containing the number of groups as described above.
- 1 ≤ T ≤ 100
- 1 ≤ N,M ≤ 1000000
Input: 3 10 2 40 4 20 3 Output: 10 32 12 Explanation Case 1 : The pairs having 2 as common factor are (4,2),(6,2),(8,2),(10,2),(2,2),(6,4), (8,6),(10,6),(10,8),(10,4)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2|
Fetching successful submissions