题目描述

传说，在上古时期存在着神秘的“数字秘境”，其中有两个古老的部族——灵火族和灵冰族，每个部族都有 $n$ 位勇士。每位勇士都拥有一块刻着神秘数字的灵石（正整数）。如果一位灵火族勇士的灵石数字 $a_i$ 和一位灵冰族勇士的灵石数字 $b_j$ 的 最大公约数 能够变成一种特殊的“回文密码”（即它的二进制表示从左往右读和从右往左读完全相同），那么这两块灵石就能产生共鸣，打开一座“数字秘境”中隐藏的宝藏库！

例如，若最大公约数为 $5$，二进制是 $101$，从两边读都一样，这就是一个回文密码；而 $6$ 的二进制是 $110$，就不是回文。

现在，你作为“数字秘境研究团队”的领队，需要统计：在所有的灵火族和灵冰族勇士之间，一共可以组成多少对能够打开宝藏库的共鸣组合？注意，每位勇士都可以与对方部族的多位勇士分别组合，我们只需计算所有满足条件的配对 $(i,j)$ 的个数。

形式化地，给定两个长度为 $n$ 的正整数序列 $a_1,a_2,…,a_n$ 和 $b_1,b_2,…,b_n$，求有多少对 $(i,j)$ 满足 $gcd⁡(a_i,b_j)$ 的二进制表示是回文串。

输入格式

第一行一个正整数 $n$，表示每个部落的勇士数量。

第二行 $n$ 个以空格隔开的正整数 $a_i$，表示灵火族勇士的灵石数字。

第三行 $n$ 个以空格隔开的正整数 $b_i$，表示灵冰族勇士的灵石数字。

输出格式

一个正整数，表示可以构成的共鸣组合的数量。

2
5 6
10 15

3

样例解释

在样例中，满足条件的共鸣组合有：(1,1)，(1,2)，(2,2)。

在c++中，可以直接调用函数__gcd(x,y)求最大公约数。

数据规模与约定

下发文件

下发文件对应子任务 $1,2,3$。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^3,1 \leq a_i,b_i \leq 10^{18}$ 。