如果对方是文艺女，你要尽可能浪漫一点,温柔一点;如果对方比较爱美爱自拍，记得多夸夸买化妆品买镜子给人家;
如果对方很御女，你要反其道而行之把她当宝宝，多摸摸头。其实啊，没有哪个女孩子不想做小宝宝，被人哄被人逗，越是女神的人，你越装逼越不看，（）（）可能更管用。
一句话，大部分女孩用她喜欢的感觉来追，少部分特殊的女孩用反其道而行之的方法来追。
oinng很喜欢小铁送给她的饭菜，所以她决定给小铁一个机会，她带着小铁来到了台球厅，异世界的台球厅的球的编号是a到b，oinng会让小铁随机挑选出两个球，如果两个球编号的最大公因数为k的话，oinng就接受小铁的表白，请问小铁能喜得女朋友吗？
输入一个数T，代表有T组输入(1<=T<=100000)
每组输入输入三个数a，b，k(1<=a<b<=1e6,a<=k<b)
每组输入输出一个数sum，代表有sum个选择使得选出来的两个球满足条件，编号a，b和b，a算一种
2 1 5 1 1 5 2
9 1