A. Common Multiple
Source: codeforces
Tags: brute force, greedy, implementation, math

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.

-----Input-----
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.

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

-----Examples-----
Input:
3
3
1 2 3
5
3 1 4 1 5
1
1
Output:
3
4
1

-----Note-----
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$.

C++ solution:
#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        unordered_set<int> distinct;
        
        for (int i = 0; i < n; ++i) {
            int num;
            cin >> num;
            distinct.insert(num);
        }
        
        cout << distinct.size() << '\n';
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	
	// Read number of test cases
	scanner.Scan()
	t, _ := strconv.Atoi(scanner.Text())

	for i := 0; i < t; i++ {
		// Skip the n line (we don't need it)
		scanner.Scan()
		
		// Read the array elements
		scanner.Scan()
		elements := strings.Fields(scanner.Text())
		
		// Count distinct elements
		unique := make(map[string]struct{})
		for _, num := range elements {
			unique[num] = struct{}{}
		}
		fmt.Println(len(unique))
	}
}

Java solution:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] elements = br.readLine().split(" ");
            Set<Integer> distinctElements = new HashSet<>();
            for (String element : elements) {
                distinctElements.add(Integer.parseInt(element));
            }
            System.out.println(distinctElements.size());
        }
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

let t;
let currentLine = 0;
let testCases = [];

rl.on('line', (line) => {
    if (currentLine === 0) {
        t = parseInt(line.trim(), 10);
    } else {
        if (currentLine % 2 === 1) {
            // Skip the 'n' line since we don't need it
        } else {
            // Process the array line
            const arr = line.trim().split(/\s+/).map(Number);
            const unique = new Set(arr);
            console.log(unique.size);
        }
    }
    currentLine++;
});

rl.on('close', () => {
    // All test cases processed
});

Python solution:
t=int(input())
for _ in range(t):
  n=int(input())
  x=list(map(int,input().split()))
  print(len(set(x)))

Ruby solution:
# Read number of test cases
t = gets.to_i

t.times do
  # Read array size (though we don't actually need it)
  n = gets.to_i
  
  # Read array elements and convert to integers
  a = gets.split.map(&:to_i)
  
  # The maximum beautiful subsequence size is the number of distinct elements
  puts a.uniq.size
end