Submit | All submissions | Best solutions | Back to list |

## HS12FACT - O-Factorial |

You are given an array of positive integers: *A* = (*A*** _{1}**,

*A*

**, ....**

_{2}*A*

**).**

_{n}Your task is to find the maximum possible *X* such that the product of all numbers from *A* is equal to *X*! * *Y*, for some positive integer *Y*.

### Input

In the first line you are given the number of test cases *T* (*T* <= 10).

Next, *T* pairs of lines follow. In the first line of each pair there is an integer *N* (1 <= *N* <= 100000) - the number of integers in *A*. In the second line you are given the elements of *A* : *A*** _{i}** (1 <= A

**<= 100000).**

_{i}### Output

For every test case, in a separate line, print the maximum possible *X*.

### Example

Input:3

5 1 2 6 60 56 6 11 19 43 6 13 25

1

24

Output:8 3 4

### Explanation

Test 1 : The product of all numbers is 40320 or 8! * 1, so the answer is 8. Test 2 : The product of all numbers is 17524650 or 3! * 2920775 so the answer is 3. Test 3 : 24 or 4!*1 so the answer is 4.

### Scoring

By solving this problem you score 10 points. Your code will be tested on 5 test sets (2 points for every correctly solved test set).

Added by: | Tata Dule |

Date: | 2012-12-05 |

Time limit: | 0.200s-0.400s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM32-GCC ASM64 GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET |

Resource: | High School Programming League 2012/13 |