Now Flash is in serious trouble. Both Reverseflash and Zoom are on their way to attack…
- User
Now Flash is in serious trouble. Both Reverse_flash and Zoom are on their way to attack him. But Flash's energy is not enough to face them. Our all time genius Harrison Wells had created a replica mixture and gave it to Flash. Now Flash got 'N' replicas of himself including him. This would have helped him to face them with the help of his replicas. But due to some chemical contamination all the replicas including original Flash were given a specific time interval to attack. They could face Reverse_flash and Zoom only if they(replicas) attack in unity. Now to test their attacks the replicas have already started attacks at t=0; Now your task is to guess the next time , other than t=0, when all the replicas could attack at once . So that you could ask Zoom and his friend to attack at that particular time :) Input constraints 1st line --> T (1 ≤ T ≤ 10) =Test cases T test cases follow: 1st line -->Integer 'N' (1 ≤ N ≤ 1000) denoting the total no. of replicas including Original Flash. Next line contains N space separated integers denoting the time intervals 'ti' (1 ≤ ti ≤ 10000) of attacks of N replicas(including Flash). Output constraints T lines --> each containing one integer denoting the answer to the above ques(modulo 1000000007).
SAMPLE INPUT 1 4 1 2 3 1
SAMPLE OUTPUT 6
Explanation
There are 4 Replicas including Flash. The attack started at t=0 i.e, everyone attacked at once for once. Now for everyone will be able to attack again at once only at t=6. Find it yourself.
Assistant
We need to read multiple test cases. For each test case, given N integers ti, the time intervals between attacks for each replica (i.e., each replica attacks at times 0, ti, 2ti, 3ti, ...). We need to find the smallest positive time t > 0 such that all replicas attack at that time. That is essentially the least common multiple (LCM) of all ti. Compute LCM of given numbers modulo 1000000007? But the output should be the answer modulo 1000000007. However, note that the LCM could be huge, beyond 64-bit, but N up to 1000, ti up to 10000. The LCM might be enormous, potentially exceeding mod. But the problem asks for the answer modulo 1000000007. But is that correct? Usually LCM is computed exactly or modulo? Since they ask "next time" it's an integer (the actual LCM). But constraints: ti up to 10000, N up to 1000, the LCM could be astronomically large (like product of many primes). However, the output is modulo 1e9+7. So we need to compute LCM modulo MOD? Wait, LCM is not a product, but can be expressed as product of primes raised to max exponents. The value can be huge. So we must compute it modulo 1e9+7. But is LCM defined modulo? The actual time t is the LCM. However, since they want the answer modulo 1e9+7, we can compute LCM modulo MOD. But careful: LCM of numbers may be such that it's bigger than MOD; but modulo works fine because we just need output modulo MOD. However, we must compute LCM exactly (maybe using prime factorization) and then reduce modulo MOD. Since ti <= 10000, we can factor each ti, take max exponent for each prime, multiply modulo MOD.
Thus solution: For each test case:
- Read N.
- Read list of t_i.
- Compute prime factorization for each t_i.
- Combine exponents: For each prime, keep max exponent across all numbers.
- Then compute result = product over primes (prime^max_exponent) % MOD.
That's straightforward.
But we need to be careful: There may be duplicates, but doesn't matter.
Edge cases: N=1 -> LCM is t1 itself. Output t1 mod MOD.
Also note: LCM of numbers up to 10000, N up to 1000, primes up to 10000. The maximum prime needed is the maximum ti. So we can precompute primes up to 10000 using sieve. Then for each ti, factorize using primes list.
Alternatively, we can compute LCM incrementally using formula LCM(a,b) = a / gcd(a,b) * b, but this can overflow if done normally, but we could use big integers (Python arbitrary-precision handles it). However, N up to 1000, ti up to 10000, the LCM could be extremely huge (like tens of thousands of digits), but Python can handle it, but time? The product of many numbers can become huge, but Python big ints multiplication is O(n log n) and could be slow if numbers become enormous. But with 1000 numbers of up to 10000, the LCM could become huge but maybe still manageable? Let's consider worst-case: all numbers are distinct primes near 10000. Then LCM is product of up to ~1229 primes (primes up to 10000 count is ~1229). Actually N is 1000, so up to 1000 distinct primes, product of 1000 primes around 10000 each. That's about log10(product) = sum log10(p) ~ 10004 = 4000 digits. That's huge but Python can handle with big integers. However, performing gcd and division on such huge numbers 1000 times may be heavy but perhaps still okay? Let's estimate: LCM via incremental method: lcm = 1, for each x: lcm = lcm * x // gcd(lcm, x). At each step, lcm grows. The numbers could become thousands of digits. gcd of two large numbers is O(n^2) maybe but Python's gcd uses binary algorithm and is efficient. Still, 1000 operations with up to 4000-digit numbers might be okay within time (typically 1-2 seconds). But T up to 10, so worst-case 101000=10,000 gcd operations on huge ints, might be slower but possibly still okay in Python? But we need modulo 1e9+7 anyway. However, if we compute exact LCM then take mod, that's one approach. But might be slower and memory heavy. Better to compute via prime factorization, which is efficient and guarantees modulo.
Given constraints ti <= 10000, we can factor each quickly.
Thus algorithm:
- Precompute list of primes up to 10000 using simple sieve.
- For each test case:
- Initialize dictionary (or array of size max_prime+1) to store max exponent.
- For each ti:
- Factor ti using primes.
- For each prime factor with exponent, update max_exponent[prime] = max(max_exponent[prime], exponent).
- Compute ans = 1
- For each prime p with exponent e:
- ans = (ans * pow(p, e, MOD)) % MOD
- Print ans
Edge Cases: Note that ti may be 1, then factorization yields no primes; that's fine. LCM will be product of others; includes 1 has no effect.
Make sure to use modulo exponentiation.
Complexity: For each ti, factorization by primes up to sqrt(ti) (primes up to 100). Actually we need to divide by all primes up to ti. Since we have primes list up to 10000, we can try dividing until p*p <= remaining, then if remaining>1 it's a prime. That's efficient. With up to 1000 numbers, each factorization costs at most number of primes up to sqrt(10000) ~ 1229? Actually primes up to 10000 count ~1229, but we only need to check primes up to sqrt(ti) (<=100). So ~25 primes? Actually pi(100) = 25. So it's trivial.
But careful: If ti is prime > 100, sqrt(ti) > 100? Actually sqrt(10000)=100, so prime >100 would have sqrt >100? For prime 9973, sqrt ~ 99.86, so sqrt <= 100. So primes up to 10000 have sqrt <= 100. So we only need to check primes up to 100. That's even smaller. Actually sqrt(10000)=100, so any composite number >10000? ti <= 10000, so sqrt <= 100. So we can check primes up to 100. But we must also capture the leftover factor after division, which could be a prime >100. For example, 101*101=10201 > 10000, so any prime >100 will appear only as a factor at most once (since square would exceed 10000). So after dividing by primes <= sqrt(remaining), if leftover >1, it's a prime factor (exponent 1). So we need primes list up to 100 for division. But we also need to store max exponents for primes that may be >100. So we need an array to map prime to exponent up to 10000. We can use dictionary.
Thus we can precompute primes up to 100 (or up to 10000) for completeness. Simpler: precompute primes up to 10000 using sieve. But for factorization, we can iterate over primes list and break when p*p > n.
Implementation steps in Python:
- MOD = 1000000007
- max_ti = 10000
- sieve to generate primes up to max_ti (maybe 10000). Actually we could generate up to 10000 to have list of all primes for factorization, but we only need up to sqrt(max_ti)=100. But generating up to 10000 is fine.
Better: generate primes up to 10000 using simple sieve, but that's quick.
However, we need to factor up to 1000 numbers, so it's fine.
Pseudo:
def sieve(limit): is_prime = [True](limit+1) is_prime[0]=is_prime[1]=False primes = [] for i in range(2, limit+1): if is_prime[i]: primes.append(i) for j in range(ii, limit+1, i): is_prime[j]=False return primes
But limit 10000, ii may overflow? Python handles; but 1000010000 = 100 million; loops might be okay but to be efficient we can do standard Sieve of Eratosthenes. Alternatively use a simple approach.
But we can also generate primes up to 100 via a small list.
Given that the constraints are small, we can precompute primes up to 10000. But it's okay.
Simplify: We'll generate primes up to 10000 and store. But we only need up to 100 for division; the leftover prime factor (if >100) will be stored as key in dict. So that's okay.
But we need to multiply pow(p, e, MOD) for all primes up to maybe 10000; we can just iterate over dict items.
Alternatively, we can compute LCM modulo using incremental method with modulo? But LCM modulo can't be computed directly via product/gcd because LCM mod MOD is not equal to (a/gcd)b mod MOD? Actually if we compute LCM exactly using formula (ab)//gcd(a,b), and we only care about modulo, we can do (a // gcd(a,b) * b) % MOD if we perform division exactly. But a and b may be huge. However, we can compute LCM under modulo by using prime factorization. So factorization is safer.
Edge Cases: Note that ti can be up to 10000, but N up to 1000. Using dict for exponents is fine.
Also note: There might be repeated ti's, but that's fine.
Now verify sample: N=4, ti = 1,2,3,1. Factorization: 1 (none), 2: 2^1, 3:3^1. Max exponents: 2^1,3^1. LCM = 6. Output 6.
Works.
Now let's consider mod: 6 mod MOD = 6.
Now what about overflow? We're using pow with mod, so fine.
Thus implement.
Potential pitfalls:
- Input reading: There may be multiple test cases; ensure we read all numbers correctly.
- For each test case, we need to clear the exponent map. We can use a dict or list of size 10001 for max exponent (initialize to 0). Since ti <= 10000, we can allocate array of size 10001 for max_exponent. That is simpler: max_exp = [0]*10001. Then for each ti, factorize and update max_exp[p] = max(max_exp[p], exp). After processing all ti, iterate p from 2 to 10000; if max_exp[p] >0, ans = ans * pow(p, max_exp[p], MOD) % MOD. This avoids dictionary overhead. But careful: For primes > 10000? Not needed. So we can do array of size 10001. Factorization will yield primes up to 10000. So that works.
But factorizing each ti: we can write a function factorize(n) that returns list of (prime, exponent). Use precomputed primes.
Precompute primes up to 100 (or up to 10000). Actually for array approach, we need to update max_exp for primes possibly up to 10000. So we need to factor all primes. If we generate primes list up to 10000, we can iterate over primes until p*p <= n, and then handle leftover. But iterating over all primes up to 10000 for each factorization (even if many primes > sqrt(n) are skipped because we break when p > sqrt(n))? But we still loop until p <= sqrt(n). Since sqrt(n) <= 100, we only need primes up to 100. So we can generate primes up to 100 and then use them for factorization; leftover > 1 will be prime up to 10000, we can directly treat as prime factor (exponent 1). That is efficient. So we can precompute primes up to 100. Let's compute primes up to 100.
Simplify: We can generate primes up to 100 via a simple function:
def primes_upto(n): sieve = [True](n+1) sieve[0]=sieve[1]=False for i in range(2, int(n**0.5)+1): if sieve[i]: for j in range(ii, n+1, i): sieve[j]=False return [i for i, is_p in enumerate(sieve) if is_p]
But we can also hardcode? Not necessary.
Let's just precompute primes up to 10000; it's easy and cost is low.
But if we precompute primes up to 10000, then factorization loop will iterate over primes list, but we will break when p > n? Actually we want to iterate while p*p <= n. For n=10000, sqrt=100, so we only need primes up to 100. But if our primes list contains many primes beyond 100, we would still iterate over them? We'll have a loop like:
for p in primes: if p*p > n: break count = 0 while n % p == 0: n //= p count+=1 if count>0: update max_exp[p]...
After loop, if n>1: update max_exp[n]...
Thus we only go through primes up to sqrt(original n) (which is at most 100). So having many extra primes in list doesn't affect because we break early. So precomputing up to 10000 is fine.
Let's decide: Precompute primes up to 10000.
Implementation steps:
- Read integer T.
- Precompute primes list up to 10000 (or maybe up to 100 to save time but not necessary). Use sieve.
- For each test case: a. Read N (maybe skip empty lines). b. Read the line of N integers. Possibly split. c. Initialize max_exp array of size 10001 with zeros. d. For each ti in list: factorize(ti): n = ti for p in primes: if p*p > n: break if n % p == 0: exp = 0 while n % p == 0: n //= p exp += 1 if exp > max_exp[p]: max_exp[p] = exp if n > 1: if max_exp[n] < 1: max_exp[n] = 1 # Actually we need to set to max( max_exp[n], 1 ) e. After processing all ti, compute ans = 1 for p in range(2, 10001): if max_exp[p] > 0: ans = (ans * pow(p, max_exp[p], MOD)) % MOD f. Print ans.
Time Complexity: O(T * (N * (number of primes up to sqrt(max_ti)) + 10000) ) ~ O(T * (N * 25 + 10000)). For T=10, N=1000, that's 10*(100025 + 10000)=10(25000+10000)=350,000, which is fine.
But note: The loop from 2 to 10000 to compute product iterates over 10000 numbers each test case. That's 10*10000=100,000, also fine. Could be optimized by storing only primes that appear, but not necessary.
However, careful: max_exp array indices up to 10000, but if n after factorization becomes a prime larger than 10000? Not possible because ti <= 10000, so leftover prime n <= 10000. So safe.
Now about mod: MOD = 1000000007.
Edge Cases: If any ti is 1, factorization yields n=1, leftover n>1? Actually after loop, n=1, no leftover. So no update.
Now verify sample: Input: 1, 4, 1 2 3 1. Factorization: For ti=1, no updates. ti=2: p=2 (primes up to 100 include 2). 2^1, max_exp[2]=1, n becomes 1. ti=3: 3^1, max_exp[3]=1. ti=1: nothing. Loop over p from 2 to 10000: p=2 exp=1 => ans=2; p=3 exp=1 => ans=6; others 0. Output 6.
Works.
Now we need to think about potential pitfalls: If there are multiple prime factors with same prime, we take max exponent. For example, ti = 4 (2^2) and ti = 2 (2^1) => max exponent = 2. So LCM includes 2^2.
Now, note that when we update max_exp for leftover prime n > 1, we must set to max(max_exp[n], 1). Because leftover may appear multiple times; we need the exponent at least 1 if any number has that prime factor; but if another number has the same prime factor with exponent more than 1? Actually if the prime > sqrt(original ti), exponent can only be 1 because square would exceed 10000. So exponent is always 1 for primes > 100. So we just need to ensure max_exp[n] = 1 if it's not already set to 1? Actually there could be two numbers both containing that prime, but exponent is always 1; so max is 1. So we set to 1.
But caution: If a number has a prime factor > 100 with exponent >1? For example, consider ti = 101^2 = 10201, which >10000, so not possible because ti <=10000. So indeed for primes > 100, exponent is at most 1.
Thus updating with max_exp[n] = max(max_exp[n], 1) works.
But what about prime = 2, which is less than 100, could have exponent up to 13 (since 2^13=8192, 2^14=16384>10000). So exponent can be >1. So we need to correctly count exponents for small primes.
Now, what about prime factor that appears both from the small prime loop and leftover? For example, if ti = 2*97, we factor: in loop, p=2 will be captured, exponent 1; then after division n becomes 97, which is > sqrt(original) maybe? sqrt(194) ~13.9, and 97 >13, so leftover = 97. So we update max_exp[97]. That's fine.
Now, what about numbers like 10000 = 2^4 * 5^4? sqrt(10000)=100, so p=2 and p=5 will be captured, exponent 4 each, n becomes 1. So leftover none.
Thus factorization works.
Now, one more nuance: When we break on condition pp > n, note that n changes during factorization, so we need to recompute pp > current n? Actually standard approach: loop over primes while p*p <= original_n? Or while p * p <= n? Usually we do while p * p <= n, because as we reduce n, the bound reduces. So we compute condition p * p <= n. That's fine.
Implementation:
def factorize(num, max_exp): n = num for p in primes: if p * p > n: break if n % p == 0: exp = 0 while n % p == 0: n //= p exp += 1 if exp > max_exp[p]: max_exp[p] = exp if n > 1: if max_exp[n] < 1: max_exp[n] = 1
But careful: In Python, max_exp is a list, so index n. n could be up to 10000. So we can directly assign: max_exp[n] = max(max_exp[n], 1). Since exponent can only be 1 for leftover.
Now, after processing all ti, compute product.
But one more nuance: Since we are using a list of length maybe 10001, indexing directly with prime numbers. That's fine.
Now, we must consider that the LCM could be modulo MOD. The product of pow(p, e, MOD) mod MOD is straightforward.
Now, test edge: T=1, N=1, ti=10000. Factorization of 10000 yields 2^4,5^4. max_exp[2]=4, max_exp[5]=4. ans = 2^4 * 5^4 = 16*625=10000. Output 10000 mod MOD = 10000. Good.
Now, test with many numbers: N=2, ti=9999 and 10000. 9999= 3^2 * 11 * 101? Actually 9999 = 91111? Let's factor: 9999 = 33* 11 * 101? 33=9, 911=99, 99*101=9999. So primes: 3^2, 11^1, 101^1. 10000 = 2^4 * 5^4. LCM = 2^4 * 5^4 * 3^2 * 11 * 101. Compute product mod. That's fine.
Now, about performance: Looping over primes up to 10000, but we break early. So primes list can be precomputed up to 10000.
Alternatively, we can precompute primes up to 100 (since sqrt(10000)=100) and use that for factorization; leftover primes >100 will be handled. That might be slightly faster. But either is fine.
I'll implement with prime list up to 10000. But I'll compute primes up to 10000 using sieve.
But note: The sieve of Eratosthenes up to 10000 is trivial.
Implementation:
def get_primes(limit): is_prime = [True](limit+1) is_prime[0]=is_prime[1]=False for i in range(2, int(limit**0.5)+1): if is_prime[i]: for j in range(ii, limit+1, i): is_prime[j]=False primes = [i for i, val in enumerate(is_prime) if val] return primes
We'll call primes = get_primes(10000) at start.
But careful: The sieve up to 10000 includes numbers up to 10000. It's fine.
But is the list of primes up to 10000 needed? Only for factorization loop; we break early, so it's okay.
However, there's a subtlety: In factorization loop, we iterate over primes, and break when p*p > n. Since primes list is sorted, that's fine.
Now, after computing max_exp, we loop over all indices 2..10000 to multiply. That includes composite indices; but we only update for prime indices? Actually max_exp for composite indices will always be 0 because we only set for primes. However, it's possible that we set for composite if leftover n is composite? But leftover n after dividing by all primes <= sqrt(original n) is either 1 or a prime number (since if n had two prime factors both > sqrt(original), their product would exceed original). Actually leftover n can be composite only if original n had a prime factor > sqrt(original) and also another factor? Let's analyze: Suppose n = p * q where p and q are primes > sqrt(original). Then p * q > sqrt(original)sqrt(original) = original, contradiction because p and q are factors of original, so original >= pq. So if both are > sqrt(original), product > original. So not possible. So leftover n is either 1 or a prime. So we only set prime indices. So looping over all numbers 2..10000 is okay, only primes have non-zero, but we can also loop over primes list to compute product to avoid checking composites. That might be slightly faster but not necessary.
But careful: We might set max_exp for a prime > 10000? Not possible.
Thus final answer.
But there is also possibility that LCM could exceed modulo, but we output modulo, so fine.
Now, confirm constraints: T up to 10, N up to 1000, ti up to 10000. So maximum LCM bits: product of distinct primes up to 10000 ~ 1229 primes. Each prime average ~5000, log10 ~3.7, so product digits ~1229*3.7 ≈ 4547 digits. That's huge but manageable? But we aren't computing that directly; we compute prime factors and multiply modulo, so fine.
Now, potential issues: In factorization for each ti, we may encounter prime 1? No.
Now, about input reading: The input format: first line T, then for each test case, first line N, next line contains N space-separated integers. We must handle multiple lines. Possibly there are extra spaces. Use sys.stdin.read() to read all and split? Or use input().
We'll use sys.stdin.buffer.read().split() to parse all tokens quickly. That might be easier.
Implementation using tokens:
import sys def main(): data = sys.stdin.buffer.read().split() it = iter(data) T = int(next(it)) MOD = 1000000007 # Precompute primes up to 10000 max_val = 10000 is_prime = [True](max_val+1) is_prime[0]=is_prime[1]=False for i in range(2, int(max_val**0.5)+1): if is_prime[i]: step = i start = ii is_prime[start:max_val+1:step] = [False]*(((max_val - start)//step)+1) primes = [i for i, v in enumerate(is_prime) if v]
out_lines = [] for _ in range(T): N = int(next(it)) max_exp = [0]*(max_val+1) for i in range(N): ti = int(next(it)) n = ti # factorize for p in primes: if p * p > n: break if n % p == 0: exp = 0 while n % p == 0: n //= p exp += 1 if exp > max_exp[p]: max_exp[p] = exp if n > 1: if max_exp[n] < 1: # exponent is 1 max_exp[n] = 1 ans = 1 for p in range(2, max_val+1): if max_exp[p]: ans = (ans * pow(p, max_exp[p], MOD)) % MOD out_lines.append(str(ans)) sys.stdout.write("\n".join(out_lines))if name == "main": main()
Potential improvements: Instead of iterating over all 2..max_val, we could iterate over primes list, but we must ensure that any prime factor > max_val? No.
But note: The primes list includes primes up to 10000; we could use that to compute ans as well: for p in primes: if max_exp[p]: ans = ans * pow(p, max_exp[p], MOD) % MOD. That would be more efficient.
Modify:
for p in primes: if max_exp[p]: ans = (ans * pow(p, max_exp[p], MOD)) % MOD
But we need to also consider primes that are >10000? Not needed.
So better.
Also note: In the factorization loop, we break when p*p > n. Since primes list is sorted, fine.
Now, one nuance: The line is_prime[start:max_val+1:step] assignment with list multiplication may be less efficient but for limit 10000 it's fine. Alternatively, use for loop.
But we can write:
for i in range(2, int(max_val**0.5)+1): if is_prime[i]: for j in range(i*i, max_val+1, i): is_prime[j] = False
That is simple.
I'll use that.
Now, edge case: When n becomes 1 after loop, we skip leftover.
Now, check for large T and N. Should be okay.
But we need to be careful: There is an assumption that each test case's numbers are all within 1..10000. Yes.
Now, confirm sample:
Input: 1 4 1 2 3 1
Our code: T=1, N=4, numbers: 1,2,3,1. max_exp initially all zero. For ti=1: factorization loop for p in primes: p=2, pp=4 >1? Actually 22=4 >1, break immediately because pp > n? condition: p * p > n, 4 >1 true, so break; n=1, leftover none. So no updates. For ti=2: n=2; loop p=2, pp=4 >2? 4>2 true? Actually p * p > n? if p*p > n then break before checking divisibility? In our loop we have:
for p in primes: if p * p > n: break if n % p == 0: ...
So for n=2, p=2: pp=4 >2 => break, so we never check divisibility for p=2. That's a problem! Because we break before processing p=2. Indeed, for n that is prime and less than pp, we break too early. The condition should be p * p > n, but we need to check divisibility for primes up to sqrt(n). But p=2 has pp=4 >2, and indeed sqrt(2) ≈1.414, so we should not check any primes because there is no prime <= sqrt(2) besides maybe 2? Actually sqrt(2) is ~1.414, so the smallest prime 2 is > sqrt(2). So indeed we should not check 2 because if n is prime and less than p^2, then it's prime. So we should break before processing p if p > sqrt(n). But note: p is the prime from the list; sqrt(n) is not necessarily an integer. The condition p * p > n ensures that p > sqrt(n). So if n is prime and p is the first prime (2), if n=2, then p=2 gives 22=4>2, break, so we don't check 2. Then leftover n=2 >1, so we treat n as prime in leftover. That is correct. So our code is fine: For n=2, loop breaks immediately, then leftover n=2 >1, so we set max_exp[2] = max(max_exp[2],1). So it's handled. Good.
Similarly for n=3, p=2: p*p=4 >3, break, leftover n=3 >1, set max_exp[3]=1. Good.
For n=4: p=2, pp=4 >4? 4 >4 is false, so we enter, because condition pp > n is false when pp == n? We have if p * p > n: break. If pp == n (4==4), we do not break; we check divisibility. That's correct. So for n=4, p=2, p*p=4, not >4, so we check n%2, find divisible, exp becomes 2, n becomes 1, then after loop, leftover none. So max_exp[2] becomes max(prev,2). That's correct.
So the factorization logic is correct.
Now, consider ti=1: n=1, p=2, p*p=4 >1, break; n=1 leftover none. So no update.
Thus works.
Now, we should consider that max_exp is a list of size 10001; we update max_exp[n] for leftover. But what if leftover n is 1? We skip.
Now, one more nuance: The leftover n might be a prime that we have already processed as part of the loop? Actually if n is reduced to 1, leftover none. If n is reduced to a prime that is > sqrt(original) but not necessarily > 100? Already handled.
Now, about the pow function: pow(p, e, MOD) is efficient.
Now, output: each answer on separate line.
Now, check for possible large test: T=10, each N=1000, each ti=10000 (which is 2^4*5^4). Then max_exp[2]=4, max_exp[5]=4 for each test, ans = 10000, output 10000 each. That's fine.
Now, consider ti=9973 (prime). Then max_exp[9973] set to 1. In the product loop, we need to multiply by pow(9973,1,MOD). That's fine.
Now, what about memory? fine.
Now, we must be careful about reading input: after reading T, then for each test, we read N, then we read N integers. They may be on same line or multiple lines. Using tokenized reading handles that.
Now, edge case: N may be 0? According to constraints, N >=1. So ok.
Now, potential optimization: Instead of iterating over all primes up to 10000 for each factorization, we could store primes up to 100. But not needed.
Now, one more nuance: The problem statement says "output answer modulo 1000000007". So we do modulo. The sample output 6, which is less than MOD.
Now, think about corner case: LCM could be 0 mod MOD? That's possible if LCM is a multiple of MOD, but we take modulo, so it's 0. But the actual next time would be that LCM, but we output modulo. The problem asks for output modulo 1000000007, so it's fine.
But is there any trick? Could the LCM be computed using Python's math.lcm? Python 3.9+ has math.lcm, which returns the LCM as an integer. However, with many numbers and large result, it may be heavy but could work. But using prime factorization is more robust.
Now, about large primes: Since we are using list index for max_exp up to 10000, it's fine.
Now, we should consider time: For each test case, we allocate max_exp list of size 10001. That's fine.
Now, one potential issue: The input might have blank lines. But token reading ignores them.
Now, implement code.
But before finalizing, test with some custom cases.
Case 1: T=1, N=2, ti=10000 9999. LCM = 2^4 5^4 3^2 11101 = compute product: 10000 * 9 * 11 * 101? Actually LCM = 10000 * 9 * 11 * 101 / gcd? Let's compute: 10000=2^45^4, 9999=3^211101. Since disjoint primes, LCM = 100009999 = 99990000. So ans = 99990000 % MOD = 99990000. Our code should give that.
Compute manually: 2^4=16, 5^4=625, 16*625=10000. Multiply by 3^2=9 => 90000, by 11 => 990000, by 101 => 99990000. So correct.
Case 2: T=1, N=3, ti=12 18 30. LCM of 12 (2^23), 18 (23^2), 30 (235) => LCM = 2^2 * 3^2 5 = 49*5=180. Output 180.
Our code: max_exp[2]=2, [3]=2, [5]=1 => product 495=180. Good.
Case 3: T=1, N=5, ti=1 1 1 1 1. LCM =1? Actually all attack at t=0, and all intervals are 1, so they attack at every integer time. The smallest positive t is 1. So answer 1. Our code: max_exp all zeros, ans remains 1. Good.
Case 4: T=1, N=2, ti=1234 5678. Factor each. Should compute LCM properly. Not necessary.
Now, also test with ti=10000 and ti=5000. 5000= 2^3 5^4? Actually 5000=5^4 * 2^3? 5^4=625, 6258=5000. So 2^3=8. So max exponents: 2^4 from 10000, 5^4 from both. LCM = 2^4*5^4=10000. Output 10000. Good.
Now, test with ti=16 (2^4) and ti=24 (2^33). LCM = 2^43=48. Good.
Now, the code seems correct.
But consider the possibility of duplicate primes: In the factorization loop for each ti, we update max_exp[p] = max(prev, exp). That's fine.
Now, consider that we update max_exp for leftover prime, and also maybe later we encounter same prime as a factor from another number with exponent >1? Not possible for primes >100 (exponent only 1). For primes <=100, they would have been captured in loop, not leftover. So no conflict.
Now, about mod multiplication: we multiply in loop and take mod.
Now, implementation details:
We'll use sys.stdin.buffer.read().split() to get all tokens. We'll map to ints.
Now, we might need to handle large T and large N quickly. Our code does.
Now, final answer.
But before finalizing, think about any pitfalls: The condition "p * p > n" inside the loop uses current n which changes during factorization of that ti (since we divide n). However, the loop condition is checked each iteration with the current n. That is correct: after we factor out p, n reduces, so the bound sqrt(n) decreases. However, the typical algorithm is to loop while p * p <= original_n? Actually many implementations loop while p * p <= n, which is fine because if after division n becomes 1, the condition will be false and loop will end. But what about case where after division, n becomes a prime that is less than pp? For example, start with n=50. p=2: pp=4 <=50, we factor out 2, n becomes 25. Next p=3: pp=9 <=25, but 3 does not divide 25. Next p=5: pp=25 <=25? 25<=25 so we check, and factor out 5, n becomes 5. Now after loop, p increments to next prime, say 7: pp=49 >5? Actually before checking p=7, we evaluate condition pp > n? 49>5 true, break. So leftover n=5 >1, so set max_exp[5]=1. That's fine.
But what about scenario where we have a prime factor that is less than the current p? That's not an issue because we process primes in increasing order.
Now, potential bug: If n becomes 1, the next p will have p*p > 1, so break. Good.
Thus algorithm stands.
Now, check with ti=9991 (a prime near 10000). For n=9991, p=2: pp=4 <=9991, but 9991%2 not 0, move on. p=3:9 <=9991, not factor. Continue up to p=97 (since 9797=9409 <=9991, 97 divides 9991? 9991/97=103? Actually 97103=9991, 103 is prime > 97. So when p=97, pp=9409 <=9991, we check divisibility, find that 9991%97==0? 97103=9991, yes. So we factor out 97, exp=1, n becomes 103. Now, p=101 next: pp=10201 > n=103? 10201>103 true, so break. Then leftover n=103>1, set max_exp[103]=1. That's correct: factors 97 and 103. Good.
Now, what about prime factor that appears squared? For example, ti=1681=41^2. sqrt(1681)=41, p up to 41. p=41: p*p=1681 <=1681, check, factor out two 41s, exp=2, n becomes 1. leftover none. So max_exp[41] updated to 2. Good.
Now, all good.
Now, about performance: In the worst case, for each ti we loop over primes up to sqrt(ti) which is at most 100, so at most 100 iterations per ti. For N=1000, that's 100k iterations. Times T=10 gives 1M. Very fast.
Now, about memory: max_exp list of 10001 ints per test case; fine.
Thus solution.
But before finalizing, consider the possibility that we could compute LCM using math.lcm (Python 3.9+). For large numbers it could be huge but maybe within memory? 5000 digits is fine for Python, but multiplication and division with gcd could be slower? But we can try, but we need modulo; we can compute exact LCM and then modulo. However, the exact LCM could have up to ~5000 digits, which is about 16KB, not huge. But for 1000 numbers, intermediate LCM may become huge early. However, Python big ints are optimized, but performing gcd with huge numbers repeatedly might be slower than factorization. But it's still possibly okay for constraints. But the factorization method is more reliable and demonstrates understanding.
We'll go with factorization.
Now, finalize the code.
I'll write with comments.
Potential improvement: Precompute primes only up to 100? But we need to handle leftover primes up to 10000; we can still handle that by setting max_exp for leftover.
Given simplicity, I'll precompute primes up to 10000.
But note: The sieve of Eratosthenes up to 10000 is fine.
Implementation details in code:
def sieve(limit): is_prime = [True](limit+1) is_prime[0]=is_prime[1]=False for i in range(2, int(limit**0.5)+1): if is_prime[i]: for j in range(ii, limit+1, i): is_prime[j] = False return [i for i in range(limit+1) if is_prime[i]]
But we can combine.
Now, I'll write final code.
Now, re-check the output format: T lines, each containing one integer.
Now, sample test: should output 6.
Now, final.
But wait, the problem statement says: "Now to test their attacks the replicas have already started attacks at t=0; Now your task is to guess the next time , other than t=0, when all the replicas could attack at once ." So we need the smallest positive t. That's LCM. Good.
Now, could there be any scenario where LCM is 0? Not possible because all ti >=1, LCM >=1.
Now, modulo: 1e9+7 is prime.
Now, possible nuance: The LCM may be extremely large, but we output modulo. So correct.
Now, final answer.
But there is one more subtlety: The problem says "output answer modulo 1000000007". Typically, if the answer is the time, which is an integer, but we output modulo. This could be because the actual LCM might be too big to output directly, so they require modulo. So our method is correct.
Now, implement.
I will write code accordingly.
Testing with some random cases manually (mentally) to ensure correctness.
Case: T=2 Test1: N=2 ti=2 4 -> LCM=4 -> output 4. Test2: N=3 ti=6 10 15 -> LCM = 30? Actually 6=23,10=25,15=35 => LCM=23*5=30 -> output 30. Our code: factorizations: 6 gives 2^1,3^1; 10 gives 2^1,5^1; 15 gives 3^1,5^1. Max exponents: 2^1,3^1,5^1 => product 30.
Case: ti=8,12,18. 8=2^3, 12=2^23, 18=23^2. LCM=2^33^2=89=72.
Works.
Now, final code.
But I want to double-check the input reading and handling of large N: Using tokens, after reading T and then reading N and then N integers, we must be careful that after reading the last test case, we have exactly the right number of tokens. The token reading approach ensures that.
Now, about potential speed: The factorization per ti might call for many primes but break early. However, for each ti we loop over primes from 2 up to sqrt(n). Since primes list includes 1229 numbers, but we break early after sqrt(n). For n=10000, sqrt=100, so we iterate over primes up to 100, which are the first 25 primes. So it's fine.
Now, after all test cases, we output.
Now, include the mod constant.
Now, check for any off-by-one: The max_exp array index up to 10000. If leftover n is exactly 10000? But if n=10000, it would have been factorized as 2^4 *5^4 and n becomes 1, so leftover none. So index 10000 never used? Actually 10000 is composite, so not a prime leftover. So maximum prime leftover can be up to 9973, which is less than 10000.
Now, but what about prime 10007? Not possible because ti max is 10000. So safe.
Now, let's think about alternative approach: Could we use the property that LCM = product / GCD of something? Not straightforward modulo.
Thus final solution.
Now, I'll produce final answer with code and explanation.
But the problem might be from some contest, and maybe there is a catch: The numbers could be large, but we have constraints small. So prime factorization is straightforward.
One more nuance: The problem might require to compute LCM of given numbers, but because the numbers represent time intervals, they may not be independent? No.
Now, I'll also consider if there is any possibility that some replica has time interval 0? But constraints say 1 ≤ ti ≤ 10000, so no.
Now, final.
Now, produce final answer with code and explanation. ```python import sys
MOD = 1000000007 MAX_VAL = 10000
def sieve(limit: int): """return list of primes up to limit""" is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(limit**0.5) + 1): if is_prime[i]: for j in range(i * i, limit + 1, i): is_prime[j] = False return [i for i, v in enumerate(is_prime) if v]
PRIMES = sieve(MAX_VAL)
def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) t = int(next(it)) out_lines = []
for _ in range(t): n = int(next(it)) # max_exp[p] = maximum exponent of prime p among all numbers max_exp = [0] * (MAX_VAL + 1) for _ in range(n): x = int(next(it)) num = x # factorize using precomputed primes for p in PRIMES: if p * p > num: break if num % p == 0: exp = 0 while num % p == 0: num //= p exp += 1 if exp > max_exp[p]: max_exp[p] = exp # remaining factor (prime > sqrt(original) or 1) if num > 1: # exponent can only be 1 if max_exp[num] < 1: max_exp[num] = 1 # compute LCM modulo MOD ans = 1 for p in PRIMES: e = max_exp[p] if e: ans = (ans * pow(p, e, MOD)) % MOD out_lines.append(str(ans)) sys.stdout.write("\n".join(out_lines))if name == "main": solve()