2017-12-03 11:37


  • as
  • 地图
  • each

Problem Description
On of Vance's favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.

In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.

Sample Input
3 4
1 2

Sample Output
Case #1: 21
Case #2: 1

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享