Cheer manages a coffee shop in Jioufen. As she is the only assistant in the shop, it is a big problem for her to mix up raw materials into a cup of coffee.
To simplify the problem, we can assume that Cheer has n kinds of raw material, and the i-th raw material has been assigned with a value a_i denoting its level of deliciousness.
For some unknown reason, Cheer believe that a kind of coffee is perfect if and only if the value of its all kinds of raw materials are co-prime with each other. A kind of perfect coffee also can be made without any of these raw materials, only by water.
Now given n kinds of raw material and their value of deliciousness, find out how many distinct kinds of perfect coffee can be made by them. Note that two kinds of coffee are considered distinct if and only if the raw material sets of them are distinct.

There are at most 75 test cases.
For each case, The first line contains one integer n indicating the number of kind of raw material.
The next line contains n integers separated by space, denoting deliciousness values: a₁, a₂, ..., a_n
(1 <= n <= 60, 1 <= a_i <= 2³¹-1)
The input ends with n = 0

For each test case, print the number of distinct kind of prefect coffee she can made in one line.

2
2 2
3
1 2 3
3
2 3 4
0

3
8
6

2013ACM-ICPC杭州赛区全国邀请赛