#CW76. 平方数(square)

平方数(square)

square

题目描述

给定 nn 个二元组 (ai,bi)(a_i,b_i)。长度为 mm 且 m>1m>1 的下标序列 p1,…,pmp_1,\ldots,p_m 是好序列,当且仅当下标互异、ap1a_{p_1} 与 bpmb_{p_m} 是完全平方数,并且每个 api+1bpia_{p_{i+1}}b_{p_i} 是完全平方数。求最小 mm,不存在时输出 −1-1。

输入格式

从square.in文件中读入。

第一行输入测试组数 TT;每组先输入 nn,再输入 nn 行的 ai,bia_i,b_i。

输出格式

从square.out文件中输出。

每组输出一行答案。

样例

样例 11 输入

3
5
4 5
20 9
8 9
16 3
12 2
1
1 1
2
1 1
1 1

样例 11 输出

2
-1
2

样例 22 输入

1
9
5 9
8 2
9 3
5 4
6 5
3 5
2 4
8 5
9 3

样例 22 输出

3

数据范围

所有数据满足 1≤n,∑n≤20001\le n,\sum n\le2000、1≤ai,bi≤1051\le a_i,b_i\le10^5。

子任务 分值 附加条件
11 2020 ∑n≤10∑n≤10
22 4040 ∑n≤400∑n≤400
33 ∑n≤2000∑n≤2000