Как вы решите следующую проблему ?

---

Алексей пытается разработать программу для очень простого микроконтроллера. Он делает показания с различных датчиков с течением времени, и эти показания должны происходить в определенное регулярное время. К сожалению, если два из этих показаний происходят одновременно, микроконтроллер зависает и должен быть сброшен.

Существует N различных датчиков, которые регулярно считывают данные. Для каждого i от 1 до N считывание с датчика i будет происходить каждые Ai миллисекунд, причем первое считывание происходит ровно через Ai миллисекунд после включения микроконтроллера. Каждое считывание занимает ровно одну миллисекунду на микроконтроллере Алексея.

Алексей хочет знать, когда микроконтроллер замерзнет после того, как он его включит.

Ввод

Первая строка входных данных содержит целое число T, обозначающее количество тестовых случаев. Описание тестов t следующим образом.

Первая строка содержит одно целое число N, обозначающее количество датчиков.

Вторая строка содержит N целых чисел через пробел A1, A2,..., обозначающих частоту измерений. А именно, датчик i будет считываться каждые миллисекунды Ai, причем первое считывание происходит через миллисекунды Ai после первого включения микроконтроллера.

Выход

Для каждого тестового случая выведите одну строку, содержащую количество миллисекунд, пока микроконтроллер не замерзнет.

Ограничения
1 ≤ T ≤ 10
2 ≤ N ≤ 500
1 ≤ Ai ≤ 10^9

Пример
Ввод:
3
3
2 3 5
4
1 8 7 11
4
4 4 5 6

Выход:
6
7
4

А ограничение по времени - 1 секунда.

Что я уже пробовал:

Я придумал следующий код :-

#include<stdio.h>
 
int main(void)
{
    int t, n, i, flag;
    scanf("%d", &t);
 
    while(t--)
    {
        scanf("%d", &n);
        long a[n], time;
 
        scanf("%ld", &a[0]);
        time = a[0];
 
        for(i = 1; i < n; i++){
            scanf("%ld", &a[i]);
 
            if(a[i] < time)
                time = a[i];
        }
 
        flag = 0;
 
        while(flag != 2)
        {
            flag = 0;
 
            for(i = 0; i < n; i++)
            {
                if(time % a[i] == 0)
                    flag++;
 
                if(flag == 2)
                    break;
 
            }
 
 
            if(flag != 2)
                time++;
 
        }
 
        printf("%ld\n", time);
    }
 
    return 0;
}

Но лимит времени в 1 секунду превышен. Может ли кто-нибудь предложить более быстрый метод решения этой проблемы ?

---