Problema da simplificação das frações

Dificuldade única

Considere uma fração no formato N/M sendo N inteiro (0<=N<=10000) e M inteiro (1<=M<=10000).

Faça um programa capaz de simplificar uma fração neste formato tal que o novo numerador e o novo denominador sejam primos entre si.

O programa receberá um conjunto de testes composto por um número indefinido de linhas. Cada linha conterá os valores de N e M separados por um espaço. O final da entrada será indicado por N=M=0.

A saída do programa deverá ser a fração simplificada na mesma ordem da entrada uma em cada linha separando-se o numerador e o denominador por espaço.

Exemplo

Entrada

0 1
1 1
2 2
2 4
9 3
25 625
0 0

Saída

0 1
1 1
1 1
1 2
3 1
1 25