题号:NC14120
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
很久以前,whalyzh同学去沙漠旅行,看到了很多很多的仙人掌,

但是现在whalyzh同学已经想不起来最酷炫的那棵仙人掌长什么样了,只记得一些特征。
小Q同学根据whalyzh同学的描述,发现这棵仙人掌可以画成一个无向的连通图,这个图不存在自环,且任意一条边至多属于一个简单环。所谓简单环,是指在图中任取一个顶点作为起点,沿着不重复的边、经过不重复的点再次走到起点的闭合路径。定义一棵仙人掌的酷炫程度为这棵仙人掌对应的图中简单环的长度最大值乘以简单环的长度最小值,如果没有环,则酷炫程度为0。
现在whalyzh同学还记得这棵仙人掌的顶点数n和边数m,你需要求出所有满足条件的仙人掌中酷炫程度的最大值。
输入描述:
第一行是一个正整数T(≤ 100000),表示测试数据的组数,
每组测试数据只有一行,包含两个整数n(2 ≤ n ≤1000000000),m(0≤ m ≤ 2000000000),表示仙人掌的顶点数和边数。
输出描述:
对于每组测试数据,输出一个整数,表示仙人掌的酷炫程度的最大值,如果不存在满足条件的仙人掌,请输出-1。
示例1
说明
对于第二组样例,满足条件的仙人掌只有一种,且无环,故酷炫程度的最大值为0。
对于第三组样例,满足条件的仙人掌只有一种,且只有一个长为2的简单环,故酷炫程度的最大值为4。