TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

40.0% (2/5)

Tags

Description

おれの財宝か?
欲しけりゃくれてやるぜ…
探してみろ
この世のすべてをそこに置いてきた

                                                                                                        <ゴール・D・ロジャー>

胖胖天-一位生於大海賊時代的年輕人,在耳聞魯夫的光榮事蹟之後,覺得魯夫實在是太帥太神勇了,所以他也決定出海成為一位海賊。

旅居海上不久,他發現了一個惡魔果實,沒想到吃下去之後身體劇變----原來是吃了一種叫打呼果實的超強果實。

因此他的絕招往往跟打呼有關,例如: 打呼死光,打呼飛彈,打呼炮擊,打呼光波,打呼光束...等等。

每個絕招都有一個固定的攻擊力值pi。

並且他的絕招往往有合成效果,每當他想使出連續技的時候,這些連續技的攻擊力會有倍增的效果,也就是連續技攻擊力 = 各個攻擊力的乘積。因為連續技基本上是一種合成技,所以與招式的發動順序無關

但是發動連續技的條件是,必須要合成技攻擊力為完全平方數才行,不然會因為非完全平方數的不穩定性,造就自身受到傷害或副作用(例如睡覺會被自己呼聲吵醒之類的XD)。

現在他想知道,他有幾種連續技可以發動,你能否幫他計算呢?

Input Format

輸入一數n(1<=n<=1000),代表絕招的數量。
接下來有n行,每行為一正整數pi(1<=pi<=10500),代表第i個攻擊的攻擊力。

註: 因為每個絕招也是由小絕招合成而來,所以對於所有的pi,不會出現>1000的質因數。

Output Format

請輸出一數,代表胖胖天有幾種連續技可以發動。

Sample Input

Sample Input #1:
7
132
1
385
30
30
35574
33

Sample Input #2:
10
1428
154
95625
11900
3185
46410
221
9438
23205
55

Sample Output

Sample Input #1:
7

Sample Input #2:
7

Hints

Sample #1 Explanation:
七種絕招攻擊力分別是:
132 = 22 * 3 * 11
1 = 1
385 = 5 * 7 * 11
30 = 2 * 3 * 5
30 = 2 * 3 * 5
35574 = 2 * 3 * 72 * 112
33 = 3 * 11

顯而可見(茶)
七種可發動連續技的攻擊力分別是:
3920400 = 132 * 1 * 30 * 30 * 33
4356 = 132 * 1 * 33
3920400 = 132 * 30 * 30 * 33
4356 = 132 * 33
1 = 1
900 = 1 * 30 * 30
900 = 30 *30

Problem Source

原TIOJ1541 / Problem Setter: math120908

Subtasks

No. Testdata Range Score
1 0 12
2 1 12
3 2 12
4 3 12
5 4 12
6 5 12
7 6 12
8 7 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8