CF2103A Common Multiple

You are given an array of integers $ a_1, a_2, \ldots, a_n $ . An array $ x_1, x_2, \ldots, x_m $ is beautiful if there exists an array $ y_1, y_2, \ldots, y_m $ such that the elements of $ y $ are distinct (in other words, $ y_i\neq y_j $ for all $ 1 \le i < j \le m $ ), and the product of $ x_i $ and $ y_i $ is the same for all $ 1 \le i \le m $ (in other words, $ x_i\cdot y_i = x_j\cdot y_j $ for all $ 1 \le i < j \le m $ ). Your task is to determine the maximum size of a subsequence $ ^{\text{∗}} $ of array $ a $ that is beautiful. $ ^{\text{∗}} $ A sequence $ b $ is a subsequence of a sequence $ a $ if $ b $ can be obtained from $ a $ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of array $ a $ . Note that there are no constraints on the sum of $ n $ over all test cases.

For each test case, output the maximum size of a subsequence of array $ a $ that is beautiful.

In the first test case, the entire array $ a = [1, 2, 3] $ is already beautiful. A possible array $ y $ is $ [6, 3, 2] $ , which is valid since the elements of $ y $ are distinct, and $ 1\cdot 6 = 2\cdot 3 = 3\cdot 2 $ . In the second test case, the subsequence $ [3, 1, 4, 5] $ is beautiful. A possible array $ y $ is $ [20, 60, 15, 12] $ . It can be proven that the entire array $ a = [3, 1, 4, 1, 5] $ is not beautiful, so the maximum size of a subsequence of array $ a $ that is beautiful is $ 4 $ .