#1871. 接连不断!
接连不断!
题目描述
青蛙有 个无向图,编号为 。每个图的点集都是 ,点集 包含 个点,编号为 。起初所有的图都没有边存在。
接下来,在编号为 的图中,对于所有在 中的编号 ,青蛙会将编号为 的点与编号为 的点连一条无向边。
他想知道这 个图中有多少个图是连通的,这个问题交给你来回答。
注:
- 表示取模, 表示 除以 得到的余数。
- 在一张图中,若在点集内任意两个不同的点 之间存在至少一条路径,则我们称这个图是连通的。
输入格式
本题有多组数据。
第一行一个整数 ,表示数据组数。
接下来 行,每行两个整数 ,含义同上。
输出格式
共 行,每行一个整数表示答案。
样例
3
3 2
4 4
5 5
1
3
2
5
4 3
4 4
4 5
4 6
4 7
2
3
3
4
4
3
1145 1499
12344 123456
114514 1919810
2
41
17
题目来源:洛谷 P10394