Problema B - Dizimação Completa

Todos sabemos que algumas fracções não têm uma representação finita com a notação decimal habitual. Por exemplo, 1/3 = 0.333... e nunca mais acabam os “3”; 1/7 = 0.142857142857... e este período “142857” repete­-se indefinidamente.

Outras têm uma representação exacta: 1/2 = 0.5; 127/128 = 0.9921875; 3/40 = 0.075.

Das que não têm representação finita há algumas que têm uma parte inicial não repetitiva a que se segue a tal parte repetitiva. Por exemplo, 8/15 = 0.5333... Neste caso a parte inicial é “5” e a parte repetitiva é “3”. Outro exemplo: 19/44 = 0.43181818... Ou seja, a parte fixa é “43” e a parte periódica é “18”.

Podemos generalizar, dizendo que qualquer fracção própria (uma fracção própria é uma fracção em que o numerador e o denominador são positivos, sendo o numerador menor do que o denominador) tem uma representação decimal com uma parte não repetitiva, a cabeça, e uma parte repetitiva, a cauda, em que uma ou outra mas não as duas podem ser vazias. No caso de 1/3 a cabeça é vazia e a cauda é “3”; no caso de 3/40 a cabeça é “075” e a cauda é vazia; no caso de 19/44 a cabeça é “43” e a cauda é “18”. Como vemos, a cabeça e a cauda das fracções próprias podem ser representados por cadeias de caracteres.

O Problema

Escreva um programa para calcular a cabeça e a cauda de uma fracção própria determinada pelo seu numerador e pelo seu denominador.

Input

O input tem várias linhas. Em cada linha vêm dois números inteiros positivos, A e B, com A < B e B ≤ 1024. O número A representa o numerador de uma fracção e o número B o denominador.

Output

O output contém tantas linhas como o input. Em cada linha aparecem, separados por um sinal de cardinal ‘#’, a cabeça e a cauda da representação decimal da fracção que vem na linha correspondente do input.

Exemplo de Input

1 3
1 7
1 2
127 128
3 40
8 15
19 44
1 61

Exemplo de Output

#3
#142857
5#
9921875#
075#
5#3
43#18
#016393442622950819672131147540983606557377049180327868852459

Qualificação para a final das ONI'2005
(21/04 a 24/04 de 2005)