The pair in the land of 1000000007 is the pair of numbers _a_ and _b_ with the following relation: a × b = 1 (mod 1000000007). It is believed to be the sign of divine. Your task is to increase the number of happy marriages so you must find the maximum number of distinct pairs! Distinct pairs can not have the same number (with the same index). Pairs are different when the sets of their indices are different
The first line contains the number of test cases _T_ (T ≤ 5). The first line of each test case contains the size of population, _n_ (1 ≤ n ≤ 30000). The following n lines contain the numbers ai (1 ≤ ai < 1000000007).
For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the maximum number of distinct pairs.
## Input
The first line contains the number of test cases _T_ (T ≤ 5). The first line of each test case contains the size of population, _n_ (1 ≤ n ≤ 30000). The following n lines contain the numbers ai (1 ≤ ai < 1000000007).
## Output
For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the maximum number of distinct pairs.
[samples]
**Definitions**
Let $ p = 1000000007 $.
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ denote the population size.
- Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ be a sequence of integers where $ 1 \le a_{k,i} < p $.
**Constraints**
1. $ 1 \le T \le 5 $
2. For each $ k \in \{1, \dots, T\} $:
- $ 1 \le n_k \le 30000 $
- $ 1 \le a_{k,i} < p $ for all $ i \in \{1, \dots, n_k\} $
**Objective**
Find the maximum number of distinct unordered pairs $ \{i, j\} $ with $ i \ne j $ such that:
$$
a_{k,i} \cdot a_{k,j} \equiv 1 \pmod{p}
$$
and no index appears in more than one pair.