<p>Given an array of positive integers <code>nums</code>, return <em>the number of <strong>distinct prime factors</strong> in the product of the elements of</em> <code>nums</code>.</p>

<p><strong>Note</strong> that:</p>

<ul>
	<li>A number greater than <code>1</code> is called <strong>prime</strong> if it is divisible by only <code>1</code> and itself.</li>
	<li>An integer <code>val1</code> is a factor of another integer <code>val2</code> if <code>val2 / val1</code> is an integer.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,3,7,10,6]
<strong>Output:</strong> 4
<strong>Explanation:</strong>
The product of all the elements in nums is: 2 * 4 * 3 * 7 * 10 * 6 = 10080 = 2<sup>5</sup> * 3<sup>2</sup> * 5 * 7.
There are 4 distinct prime factors so we return 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,8,16]
<strong>Output:</strong> 1
<strong>Explanation:</strong>
The product of all the elements in nums is: 2 * 4 * 8 * 16 = 1024 = 2<sup>10</sup>.
There is 1 distinct prime factor so we return 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>2 &lt;= nums[i] &lt;= 1000</code></li>
</ul>

masks = [
    0, 0, 1, 2, 1, 4, 3, 8, 1, 2, 5, 16, 3, 32, 9, 6, 1, 64, 3, 128, 5, 10, 17, 256, 3, 4, 33, 2, 9, 512,
    7, 1024, 1, 18, 65, 12, 3, 2048, 129, 34, 5, 4096, 11, 8192, 17, 6, 257, 16384, 3, 8, 5, 66, 33, 32768,
    3, 20, 9, 130, 513, 65536, 7, 131072, 1025, 10, 1, 36, 19, 262144, 65, 258, 13, 524288, 3, 1048576, 2049,
    6, 129, 24, 35, 2097152, 5, 2, 4097, 4194304, 11, 68, 8193, 514, 17, 8388608, 7, 40, 257, 1026, 16385,
    132, 3, 16777216, 9, 18, 5, 33554432, 67, 67108864, 33, 14, 32769, 134217728, 3, 268435456, 21, 2050,
    9, 536870912, 131, 260, 513, 34, 65537, 72, 7, 16, 131073, 4098, 1025, 4, 11, 1073741824, 1, 8194, 37,
    2147483648, 19, 136, 262145, 6, 65, 4294967296, 259, 8589934592, 13, 16386, 524289, 48, 3, 516, 1048577,
    10, 2049, 17179869184, 7, 34359738368, 129, 66, 25, 1028, 35, 68719476736, 2097153, 32770, 5, 264, 3,
    137438953472, 4097, 22, 4194305, 274877906944, 11, 32, 69, 130, 8193, 549755813888, 515, 12, 17, 65538,
    8388609, 1099511627776, 7, 2199023255552, 41, 131074, 257, 2052, 1027, 80, 16385, 10, 133, 4398046511104,
    3, 8796093022208, 16777217, 38, 9, 17592186044416, 19, 35184372088832, 5, 262146, 33554433, 520, 67, 4100,
    67108865, 258, 33, 144, 15, 70368744177664, 32769, 524290, 134217729, 8196, 3, 1032, 268435457, 1048578,
    21, 96, 2051, 140737488355328, 9, 6, 536870913, 281474976710656, 131, 562949953421312, 261, 26, 513, 1125899906842624,
    35, 16388, 65537, 2097154, 73, 2251799813685248, 7, 4503599627370496, 17, 2, 131073, 12, 4099, 160, 1025,
    4194306, 5, 9007199254740992, 11, 272, 1073741825, 70, 1, 18014398509481984, 8195, 2056, 37, 514, 2147483649,
    36028797018963968, 19, 32772, 137, 8388610, 262145, 72057594037927936, 7, 144115188075855872, 65, 42,
    4294967297, 20, 259, 288230376151711744, 8589934593, 1026, 13, 576460752303423488, 16387, 1152921504606846976,
    524289, 134, 49, 4104, 3, 64, 517, 16777218, 1048577, 2305843009213693952, 11, 65540, 2049, 18, 17179869185,
    288, 7, 8200, 34359738369, 33554434, 129, 131076, 67, 4611686018427387904, 25, 67108866, 1029, 9223372036854775808,
    35, 18446744073709551616, 68719476737, 14, 2097153, 36893488147419103232, 32771, 528, 5, 134217730, 265,
    192, 3, 36, 137438953473, 268435458, 4097, 16392, 23, 73786976294838206464, 4194305, 2050, 274877906945,
    262148, 11, 147573952589676412928, 33, 536870914, 69, 1040, 131, 8, 8193, 262, 549755813889, 295147905179352825856,
    515, 590295810358705651712, 13, 34, 17, 1180591620717411303424, 65539, 524292, 8388609, 74, 1099511627777,
    2361183241434822606848, 7, 128, 2199023255553, 18, 41, 1048580, 131075, 4722366482869645213696, 257, 4098,
    2053, 32776, 1027, 9444732965739290427392, 81, 6, 16385, 544, 11, 18889465931478580854784, 133, 1073741826,
    4398046511105, 37778931862957161709568, 3, 28, 8796093022209, 8194, 16777217, 75557863725914323419136,
    39, 320, 9, 2147483650, 17592186044417, 2097156, 19, 151115727451828646838272, 35184372088833, 138, 5,
    302231454903657293676544, 262147, 1056, 33554433, 6, 521, 2064, 67, 604462909807314587353088, 4101, 4294967298,
    67108865, 65544, 259, 4194308, 33, 8589934594, 145, 1208925819614629174706176, 15, 2417851639229258349412352,
    70368744177665, 16386, 32769, 68, 524291, 131080, 134217729, 50, 8197, 4835703278458516698824704, 3, 9671406556917033397649408,
    1033, 518, 268435457, 384, 1048579, 19342813113834066795298816, 21, 10, 97, 38685626227668133590597632,
    2051, 8388612, 140737488355329, 17179869186, 9, 77371252455336267181195264, 7, 4112, 536870913, 34359738370,
    281474976710657, 44, 131, 154742504910672534362390528, 562949953421313, 66, 261, 309485009821345068724781056,
    27, 618970019642690137449562112, 513, 1030, 1125899906842625, 1237940039285380274899124224, 35, 262152,
    16389, 68719476738, 65537, 8208, 2097155, 132, 73, 32770, 2251799813685249, 2475880078570760549798248448,
    7, 2080, 4503599627370497, 266, 17, 16777220, 3, 4951760157141521099596496896, 131073, 137438953474, 13,
    9903520314283042199192993792, 4099, 576, 161, 22, 1025, 524296, 4194307, 19807040628566084398385987584,
    5, 274877906946, 9007199254740993, 39614081257132168796771975168, 11, 33554436, 273, 34, 1073741825, 79228162514264337593543950336,
    71, 1048584, 1, 130, 18014398509481985, 67108868, 8195, 16400, 2057, 549755813890, 37, 158456325028528675187087900672,
    515, 316912650057057350374175801344, 2147483649, 14, 36028797018963969, 1088, 19, 256, 32773, 65538, 137,
    4128, 8388611, 134217732, 262145, 1099511627778, 72057594037927937, 24, 7, 633825300114114700748351602688,
    144115188075855873, 2199023255554, 65, 268435460, 43, 1267650600228229401496703205376, 4294967297, 131074,
    21, 640, 259, 2097160, 288230376151711745, 2054, 8589934593, 2535301200456458802993406410752, 1027, 8224,
    13, 82, 576460752303423489, 5070602400912917605986812821504, 16387, 536870916, 1152921504606846977, 10,
    524289, 10141204801825835211973625643008, 135, 20282409603651670423947251286016, 49, 4398046511106, 4105,
    260, 3, 40564819207303340847894502572032, 65, 8796093022210, 517, 4194312, 16777219, 32784, 1048577, 38,
    2305843009213693953, 81129638414606681695789005144064, 11, 1152, 65541, 17592186044418, 2049, 162259276829213363391578010288128,
    19, 76, 17179869185, 35184372088834, 289, 324518553658426726783156020576256, 7, 649037107316853453566312041152512,
    8201, 262146, 34359738369, 20, 33554435, 1298074214633706907132624082305024, 129, 522, 131077, 16416,
    67, 2596148429267413814265248164610048, 4611686018427387905, 4102, 25, 5192296858534827628530496329220096,
    67108867, 10384593717069655257060992658440192, 1029, 258, 9223372036854775809, 8388616, 35, 4, 18446744073709551617,
    146, 68719476737, 2112, 15, 20769187434139310514121985316880384, 2097153, 70368744177666, 36893488147419103233,
    1073741828, 32771, 40, 529, 524290, 5, 41538374868278621028243970633760768, 134217731, 83076749736557242056487941267521536,
    265, 8198, 193, 166153499473114484112975882535043072, 3, 65552, 37, 1034, 137438953473, 332306998946228968225951765070086144,
    268435459, 2147483652, 4097, 1048578, 16393, 664613997892457936451903530140172288, 23, 1329227995784915872903807060280344576,
    73786976294838206465, 98, 4194305, 140, 2051, 768, 274877906945, 140737488355330, 262149, 131088, 11,
    2658455991569831745807614120560689152, 147573952589676412929, 6, 33, 5316911983139663491615228241121378304,
    536870915, 16777224, 69, 281474976710658, 1041, 10633823966279326983230456482242756608, 131, 4294967300,
    9, 562949953421314, 8193, 32800, 263, 21267647932558653966460912964485513216, 549755813889, 26, 295147905179352825857,
    8589934596, 515, 4160, 590295810358705651713, 1125899906842626, 13, 42535295865117307932921825928971026432,
    35, 2176, 17, 16390, 1180591620717411303425, 33554440, 65539, 85070591730234615865843651857942052864,
    524293, 2097154, 8388609, 1280, 75, 52, 1099511627777, 2251799813685250, 2361183241434822606849, 170141183460469231731687303715884105728,
    7, 67108872, 129, 4503599627370498, 2199023255553, 516, 19, 340282366920938463463374607431768211456, 41,
    2, 1048581, 8256, 131075, 680564733841876926926749214863536422912, 4722366482869645213697, 14, 257, 262160,
    4099, 1361129467683753853853498429727072845824, 2053, 162, 32777, 2722258935367507707706996859454145691648,
    1027, 17179869188, 9444732965739290427393, 4194306, 81, 134217736, 7, 5444517870735015415413993718908291383296,
    16385, 9007199254740994, 545, 34359738372, 11, 10889035741470030830827987437816582766592, 18889465931478580854785,
    274, 133, 21778071482940061661655974875633165533184, 1073741827, 268435464, 4398046511105, 70, 37778931862957161709569,
    65568, 3, 43556142965880123323311949751266331066368, 29, 18014398509481986, 8796093022209, 87112285931760246646623899502532662132736,
    8195, 1028, 16777217, 2058, 75557863725914323419137, 4224, 39, 524304, 321, 514, 9, 68719476740, 2147483651,
    174224571863520493293247799005065324265472, 17592186044417, 36028797018963970, 2097157, 536870920, 19,
    131104, 151115727451828646838273, 32774, 35184372088833, 348449143727040986586495598010130648530944, 139,
    16448, 5, 8388610, 302231454903657293676545, 1048592, 262147, 268, 1057, 72057594037927938, 33554433,
    696898287454081973172991196020261297061888, 7, 1393796574908163946345982392040522594123776, 521, 144115188075855874,
    2065, 137438953476, 67, 8320, 604462909807314587353089, 42, 4101, 2787593149816327892691964784081045188247552,
    4294967299, 5575186299632655785383929568162090376495104, 67108865, 22, 65545, 11150372599265311570767859136324180752990208,
    259, 22300745198530623141535718272648361505980416, 4194309, 288230376151711746, 33, 72, 8589934595, 274877906948,
    145, 1026, 1208925819614629174706177, 44601490397061246283071436545296723011960832, 15, 512, 2417851639229258349412353,
    576460752303423490, 70368744177665, 36, 16387, 24, 32769, 1152921504606846978, 69, 2304, 524291, 89202980794122492566142873090593446023921664,
    131081, 134, 134217729, 178405961588244985132285746181186892047843328, 51, 356811923176489970264571492362373784095686656,
    8197, 4106, 4835703278458516698824705, 713623846352979940529142984724747568191373312, 3, 549755813892,
    9671406556917033397649409, 66, 1033, 2097168, 519, 262176, 268435457, 16777218, 385, 12, 1048579, 1427247692705959881058285969449495136382746624,
    19342813113834066795298817, 2305843009213693954, 21, 2854495385411919762116571938898990272765493248, 11,
    5708990770823839524233143877797980545530986496, 97, 65542, 38685626227668133590597633, 11417981541647679048466287755595961091061972992,
    2051, 1073741832, 8388613, 18, 140737488355329, 16512, 17179869187, 1099511627780, 9, 290, 77371252455336267181195265,
    1536, 7, 32832, 4113, 8202, 536870913, 2199023255556, 34359738371, 22835963083295358096932575511191922182123945984,
    281474976710657, 33554434, 45, 45671926166590716193865151022383844364247891968, 131, 4194320, 154742504910672534362390529,
    131078, 562949953421313, 2147483656, 67, 91343852333181432387730302044767688728495783936, 261, 4611686018427387906,
    309485009821345068724781057, 524320, 27, 2052, 618970019642690137449562113, 67108866, 513, 182687704666362864775460604089535377456991567872,
    1031, 136, 1125899906842625, 9223372036854775810, 1237940039285380274899124225, 84, 35, 365375409332725729550921208179070754913983135744,
    262153, 18446744073709551618, 16389, 730750818665451459101842416358141509827966271488, 68719476739, 4352,
    65537, 14, 8209, 1461501637330902918203684832716283019655932542976, 2097155, 1048608, 133, 36893488147419103234,
    73, 2923003274661805836407369665432566039311865085952, 32771, 4398046511108, 2251799813685249, 530, 2475880078570760549798248449,
    4294967304, 7, 1024, 2081, 134217730, 4503599627370497, 8796093022212, 267, 5846006549323611672814739330865132078623730171904,
    17, 194, 16777221, 11692013098647223345629478661730264157247460343808, 3, 8589934600, 4951760157141521099596496897,
    38, 131073, 23384026197294446691258957323460528314494920687616, 137438953475, 8388624, 13, 268435458,
    9903520314283042199192993793, 46768052394588893382517914646921056628989841375232, 4099, 17592186044420,
    577, 16394, 161, 8448, 23, 93536104789177786765035829293842113257979682750464, 1025, 73786976294838206466,
    524297, 35184372088836, 4194307, 187072209578355573530071658587684226515959365500928, 19807040628566084398385987585, 2050, 5,
]

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        mask = 0
        for num in nums:
            mask |= masks[num]
        return bin(mask).count("1")
        
145