{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"A set of integers is called prime independent if none of its member is a prime multiple of another member. An integer **a** is said to be a **prime multiple** of **b** if,\n\n**a \u003d b x k** (where **k** is a prime [1])\n\nSo, **6** is a prime multiple of **2**, but **8** is not. And for example, **{2, 8, 17}** is prime independent but **{2, 8, 16}** or **{3, 6}** are not.\n\nNow, given a set of distinct positive integers, calculate the largest prime independent subset."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 20)**, denoting the number of test cases.\n\nEach case starts with an integer **N (1 \u0026le; N \u0026le; 40000)** denoting the size of the set. Next line contains **N** integers separated by a single space. Each of these **N** integers are distinct and between **1** and **500000** inclusive."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the size of the largest prime independent subset."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n5\n2 4 8 16 32\n5\n2 3 4 6 9\n3\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3\nCase 2: 3\nCase 3: 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"1. An integer is said to be a prime if it\u0027s divisible by exactly two distinct integers. First few prime numbers are **2, 3, 5, 7, 11, 13, ...**\n2. Dataset is huge, use faster I/O methods."}}]}