#948. [SDOI2013] 项链
[SDOI2013] 项链
题目背景
项链作为人体的装饰品之一,是最早出现的首饰。项链除了具有装饰功能之外,有些项链还具有特殊的显示作用,如天主教徒的十字架链和佛教徒的念珠。
从古至今人们为了美化人体本身,也美化环境,制造了各种不同风格、不同特点、不同样式的项链,满足了不同肤色、不同民族、不同审美观的人的审美需要。就材料而论,首饰市场上的项链有黄金、白银、珠宝等几种。
珍珠项链为珍珠制成的饰品,即将珍珠钻孔后用线串在一起,佩戴于项间,天然珍珠项链具有一定的护养作用。
题目描述
最近,铭铭迷恋上了一种项链。与其他珍珠项链基本上相同,不过这种项链的珠子却与众不同,是正三菱柱的泰山石雕刻而成的。
三菱柱的侧面是由正方形构成的,每个侧面都刻有数字。能够让铭铭满意的项链必须满足以下条件:
-
这串项链由 颗珠子构成。
-
每一个珠子上面的每个数字 ,必须满足 ,且珠子上面三个数字的最大公约数要恰好为 。
-
相邻的两个珠子必须不同。两个珠子被认为是相同的,当且仅当它们经过旋转,或者翻转后能够变成一样的。
-
两串项链如果能够经过旋转变成一样的,那么这两串项链被认为是相同的。
铭铭很好奇如果给定 和 ,能够找到多少串不同的项链。由于答案可能很大,所以输出答案模上 的值。
输入格式
本题有多组数据。
第一行给定一个整数 ,表示数据组数。
接下来 行,每行两个整数 和 。
输出格式
对于每组数据输出一个整数,表示有多少串不同的项链。
1
2 2
3
提示
满足条件的珠子共有三种:[1,1,1]
,[1,1,2]
,[1,2,2]
。
组成的满足条件的串有:[1,2]
,[1,3]
,[2,3]
。
对于 的数据,保证 ,,。