#P18847. [Croatian CPC2022] Komični Kvadrat

[Croatian CPC2022] Komični Kvadrat

Komični Kvadrat

题目描述

Patrick 发现,6,10,156,10,15 都不是完全平方数,但它们的乘积 6×10×15=9006\times10\times15=900 却是完全平方数。

如果一个集合中所有元素的乘积是完全平方数,就称这个集合为有趣的集合。

给定一个整数区间 [a,b][a,b],请从集合 {a,a+1,…,b}\{a,a+1,\ldots,b\} 中选择一个非空子集,使其元素乘积等于某个整数 kk 的平方,并且让正整数 kk 尽可能小。每个整数至多选择一次。

如果不存在这样的子集,请报告无解。

输入格式

第一行包含一个整数 tt,表示测试用例数量。

接下来 tt 行,每行包含两个整数 ai,bia_i,b_i,表示一个闭区间。

输出格式

对每个测试用例输出一行:如果有解,输出最小的正整数 kk;否则输出小写字符串 nema。

数据范围

  • 1≤t≤1501\le t\le150;
  • 1<ai<bi≤49001<a_i<b_i\le4900;
  • 如果有解,最小的 kk 保证小于 2632^{63}。

样例 1

输入

3
21 57
305 307
3722 3799

输出

5
nema
52898171040