Әлия мен Базарбек сандармен ойнайды. Ойындардың бірінде олардың әрқайсысы бір санды жасырды: Әлия – \(A\) саны, Базарбек – \(B\) саны. Содан кейін әрқайсысы тақтаға өз санының бөлгіштерінің санын есептеп, \(x\) және \(y\) сандарын жазды. Бұл қызықты ойынның мәнін басқа уақытта айтамыз. Олар кеткен соң Сайбар келіп тақтадағы сандарды көрді. Сайбар бұл ойынды білгенімен, Әлия мен Базарбек болжаған сандарды білмеді. Оған қызық болды — \(A \cdot B\) санының бөлгіштерінің ең аз саны қанша болуы мүмкін? Сайбар есептерді дайындаумен айналысатындықтан, оның қызығушылығын қанағаттандыруға көмектесіңіз.

Енгізу

Әр тест бірнеше кіріс деректер жиынтығынан тұрады. Бірінші жолда бір бүтін сан \(t\) (\(1 \le t \le 1000\)) — кіріс деректер жиынтығының саны. Әрі қарай кіріс деректер жиынтығының сипаттамасы беріледі.

Әрбір деректер жиынтығының жалғыз жолы екі бүтін санды қамтиды \(x\) және \(y\) (\(1 \le x, y \le 10^9\)).

Шығару

Әр деректер жиынтығы үшін бір бүтін санды шығарыңыз — жасырылған сандардың көбейтіндісінің бөлгіштерінің минималды мүмкін саны.

Мысалдар

Енгізу 1

3
1 1
3 1
2 3

Жауап 1

1
3
4