Given an array $A$ consisting of non-negative 32-bit integers. Two integers in the array are considered similar if one number can be obtained from the other by performing some cyclic shift operations (which may not be performed at all).
For example, for the positive integer $5$ with a binary representation of `0000 0000 0000 0000 0000 0000 0000 0101`:
- After one right cyclic shift, we get the number `1000 0000 0000 0000 0000 0000 0000 0010`.
- After one left cyclic shift, we get the number `0000 0000 0000 0000 0000 0000 0000 1010`.
Count the number of pairs $i < j$ such that $A_i$ and $A_j$ are two similar numbers.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ non-negative integers $A_i$.
### Output
- Output an integer representing the number of pairs of similar numbers.
### Constraints
- $1 \le n \le 10^5$.
- $0 \le A_i < 2^{32}$.
### Example
Input:
```
7
128 786432 131072 1610612736 1536 4194304 50331648
```
Output:
```
9
```
