## Algorithm

A pair of numbers has a unique LCM but a single number can be the LCM of more than one possible pairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, the number of different integer pairs with LCM is equal to N can be called the LCM cardinality of that number N. In this problem your job is to find out the LCM cardinality of a number. Input The input file contains at most 101 lines of inputs. Each line contains an integer N (0 < N ≤ 2 ∗ 109 ). Input is terminated by a line containing a single zero. This line should not be processed. Output For each line of input except the last one produce one line of output. This line contains two integers N and C. Here N is the input number and C is its cardinality. These two numbers are separated by a single space.

Sample Input 2 12 24 101101291 0

Sample Output 2 2 12 8 24 11 101101291 5

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b){
return a==0 ? b : gcd(b%a, a);
}
int lcm(int a, int b){
return a*(b/gcd(a, b));
}

int main()
{
int val;
while(scanf("%d",&val), val!=0){
vector<int> divisor;
// generate all divisor
for(int i=1;i i+It =sqrt(val);i++)
if(val%i == 0){
divisor.push_back(i);
if(val/i != i) divisor.push_back(val/i);
}
// iterate through all pairs of divisor
int res = 0;
for(int i=0;i i+It divisor.size();i++)
for(int j=i;j i+It divisor.size();j++)
if(lcm(divisor[i],divisor[j]) == val)
res++;
printf("%d %d\n",val,res);
}
}
```
```
Copy The Code &

Input

cmd
2
12
24
101101291
0

Output

cmd
2 2< br> 12 8
24 11
101101291 5