A pair of numbers has a unique LCM but a single number can be theLCM of more than one possible pairs. Forexample 12 is theLCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, the number of different integer pairs withLCM is equal toN can be called the LCM cardinality of that numberN. In this problem your job is to find outthe LCM cardinality ofa number.

Input

The input file contains at most 101 lines of inputs. Each line contains an integer N (0<N<=2*10⁹). Input is terminated by a linecontaining a single zero. This line should not be processed.

Output

For each lineof input except the last one produce one line of output. This line contains twointegersN and C. Here N is the input number andCis its cardinality. These two numbers are separated by a single space.

SampleInput                             Outputfor Sample Input

2

12

24

101101291

0

Problemsetter: Shahriar Manzoor

Special Thanks: Derek Kisman

题意：给你n，统计有多少个整数对a<=b，满足lcm(a, b) = n，

思路：枚举所有的因子计算

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;

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

ll n;

int main() {
	while (scanf("%lld", &n) != EOF && n) {
		vector<ll> ve;
		for (ll i = 1; i * i <= n; i++) {
			if (n % i == 0) {
				ve.push_back(i);
				if (i * i != n)
					ve.push_back(n/i);
			}
		}	
		ll size = ve.size();
		ll ans = 0;
		for (ll i = 0; i < size; i++)
			for (ll j = i; j < size; j++)
				if (lcm(ve[i], ve[j]) == n)
					ans++;
		printf("%lld %lld\n", n, ans);
	}	
	return 0;
}