SQFFACT - Square-free Integers Factorization

no tags 

Given the positive integers N = p1 * p2 * ... * pk and M = (p1 - 1) * (p2 - 1) * ... * (pk - 1), i.e. M = φ(N) (Euler's totient function), where k ≥ 1, pi ≠ pj for all i ≠ j with i, j = 1, 2 ... k and pi is prime number for all i = 1, 2 ... k, your task is factor n.

Input

The first line contains a positive integer T, the number of test cases, where T ≤ 100. The following T lines each contains two numbers N and M in this order, where N < 10100.

Output

Output T lines, with prime factorization of N according with example.

Example

Input:
3
210 48
983 982
14351 14112

Output:
210 = 2 * 3 * 5 * 7
983 = 983
14351 = 113 * 127

hide comments
[Lakshman]: 2015-12-23 11:14:46

What is the upper bound for P can it be <=10^100.

abhijith reddy d: 2011-05-06 20:14:48

+1 .. i dont see any point in allowing java and not allowing other languages (that support big integers)

numerix: 2011-05-06 20:14:48

Then could you please open it for all/more languages?

Paulo Roberto Santos de Sousa: 2011-05-06 20:14:48

None special reason!

Last edit: 2010-02-05 22:33:27
numerix: 2011-05-06 20:14:48

Why the language restrictions?


Added by:Paulo Roberto Santos de Sousa
Date:2010-01-18
Time limit:1.355s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 BASH BF CSHARP CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JS-RHINO LUA NEM NICE OCAML PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:Own problem