150418

Ruby


Lucas、Perrin そして McIrvin（剰余について）

Ln mod nの個数を出力してみる。
（ただし、最初の２項は除く。）

n = 3 * 10 ** 6
ary0 = Array.new(n, 0)
a, b = 1, 2
i = 1
while i < n
  a, b = a + b, a
  i += 1
  j = a % i
  ary0[j] += 1
end
p ary0[0..500].map.with_index{|n, i| [i, n]}

出力結果
[[0, 23], [1, 216979], [2, 4117], [3, 114524], [4, 39434], [5, 2], [6, 7], [7, 6
0806], [8, 1], [9, 1], [10, 3], [11, 24795], [12, 1], [13, 2], [14, 7], [15, 4],
 [16, 1], [17, 3], [18, 42262], [19, 2], [20, 1], [21, 1], [22, 11], [23, 6], [2
4, 6], [25, 1], [26, 4], [27, 7], [28, 3], [29, 9168], [30, 3], [31, 6], [32, 1]
, [33, 0], [34, 13], [35, 4], [36, 8], [37, 1], [38, 4], [39, 2], [40, 1], [41,
7], [42, 0], [43, 5], [44, 3], [45, 4], [46, 4], [47, 32674], [48, 4], [49, 3],
[50, 11], [51, 3], [52, 0], [53, 4], [54, 8], [55, 5], [56, 1], [57, 0], [58, 3]
, [59, 12], [60, 2], [61, 8], [62, 4], [63, 8], [64, 4], [65, 5], [66, 9], [67,
4], [68, 0], [69, 3], [70, 10], [71, 4], [72, 1], [73, 10], [74, 5], [75, 3], [7
6, 14615], [77, 2], [78, 3], [79, 9], [80, 2], [81, 3], [82, 4], [83, 7], [84, 2
], [85, 2], [86, 6], [87, 4], [88, 2], [89, 6], [90, 4], [91, 9], [92, 0], [93,
4], [94, 10], [95, 19], [96, 2], [97, 1], [98, 10], [99, 3], [100, 1], [101, 1],
 [102, 7], [103, 15], [104, 1], [105, 4], [106, 10], [107, 4], [108, 21], [109,
2], [110, 1], [111, 4], [112, 0], [113, 7], [114, 4], [115, 6], [116, 2], [117,
5], [118, 4], [119, 12], [120, 9], [121, 4], [122, 8], [123, 26810], [124, 0], [
125, 2], [126, 5], [127, 66], [128, 0], [129, 4], [130, 4], [131, 6], [132, 1],
[133, 1], [134, 3], [135, 3], [136, 4], [137, 4], [138, 2], [139, 8], [140, 5],
[141, 2], [142, 6], [143, 4], [144, 5], [145, 3], [146, 12], [147, 14], [148, 0]
, [149, 4], [150, 4], [151, 3], [152, 0], [153, 4], [154, 7], [155, 5], [156, 2]
, [157, 11], [158, 5], [159, 7], [160, 1], [161, 8], [162, 5], [163, 5], [164, 1
], [165, 2], [166, 7], [167, 18], [168, 3], [169, 5], [170, 6], [171, 4], [172,
2], [173, 4], [174, 2], [175, 4], [176, 6], [177, 2], [178, 1], [179, 4], [180,
3], [181, 7], [182, 0], [183, 3], [184, 4], [185, 4], [186, 4], [187, 2], [188,
5], [189, 2], [190, 2], [191, 11], [192, 3], [193, 4], [194, 32], [195, 1], [196
, 2], [197, 5], [198, 35], [199, 6057], [200, 4], [201, 3], [202, 7], [203, 5],
[204, 4], [205, 2], [206, 6], [207, 15], [208, 1], [209, 1], [210, 3], [211, 10]
, [212, 1], [213, 1], [214, 6], [215, 10], [216, 9], [217, 3], [218, 3], [219, 0
], [220, 3], [221, 14], [222, 3], [223, 14], [224, 6], [225, 2], [226, 2], [227,
 12], [228, 5], [229, 4], [230, 1], [231, 9], [232, 3], [233, 3], [234, 5], [235
, 6], [236, 4], [237, 1], [238, 6], [239, 9], [240, 3], [241, 2], [242, 10], [24
3, 4], [244, 1], [245, 2], [246, 4], [247, 12], [248, 1], [249, 3], [250, 3], [2
51, 9], [252, 6], [253, 3], [254, 4], [255, 13], [256, 6], [257, 2], [258, 5], [
259, 5], [260, 2], [261, 4], [262, 5], [263, 4], [264, 7], [265, 9], [266, 7], [
267, 3], [268, 1], [269, 7], [270, 9], [271, 6], [272, 2], [273, 4], [274, 6], [
275, 12], [276, 2], [277, 3], [278, 2], [279, 8], [280, 2], [281, 6], [282, 2],
[283, 3], [284, 5], [285, 2], [286, 9], [287, 14], [288, 13], [289, 5], [290, 9]
, [291, 4], [292, 3], [293, 5], [294, 6], [295, 3], [296, 0], [297, 0], [298, 1]
, [299, 3], [300, 3], [301, 2], [302, 5], [303, 1], [304, 3], [305, 6], [306, 2]
, [307, 4], [308, 1], [309, 1], [310, 0], [311, 17], [312, 2], [313, 5], [314, 1
2], [315, 11], [316, 1], [317, 3], [318, 8], [319, 31], [320, 2], [321, 2], [322
, 23224], [323, 4], [324, 5], [325, 2], [326, 4], [327, 12], [328, 3], [329, 4],
 [330, 0], [331, 2], [332, 1], [333, 6], [334, 2], [335, 3], [336, 5], [337, 7],
 [338, 10], [339, 3], [340, 3], [341, 5], [342, 4], [343, 8], [344, 2], [345, 4]
, [346, 8], [347, 6], [348, 4], [349, 2], [350, 3], [351, 4], [352, 3], [353, 4]
, [354, 3], [355, 2], [356, 6], [357, 3], [358, 4], [359, 5], [360, 8], [361, 4]
, [362, 14], [363, 5], [364, 9], [365, 4], [366, 2], [367, 20], [368, 4], [369,
4], [370, 2], [371, 6], [372, 2], [373, 6], [374, 5], [375, 5], [376, 2], [377,
7], [378, 4], [379, 7], [380, 2], [381, 3], [382, 6], [383, 12], [384, 6], [385,
 1], [386, 11], [387, 3], [388, 1], [389, 5], [390, 2], [391, 1], [392, 3], [393
, 2], [394, 3], [395, 6], [396, 3], [397, 0], [398, 4], [399, 11], [400, 7], [40
1, 5], [402, 4], [403, 3], [404, 1], [405, 4], [406, 5], [407, 11], [408, 3], [4
09, 9], [410, 3], [411, 2], [412, 2], [413, 2], [414, 4], [415, 12], [416, 2], [
417, 2], [418, 4], [419, 4], [420, 3], [421, 8], [422, 1], [423, 6], [424, 3], [
425, 3], [426, 2], [427, 11], [428, 3], [429, 1], [430, 9], [431, 6], [432, 9],
[433, 2], [434, 9], [435, 3], [436, 2], [437, 6], [438, 2], [439, 15], [440, 3],
 [441, 3], [442, 4], [443, 3], [444, 3], [445, 5], [446, 2], [447, 30], [448, 4]
, [449, 2], [450, 4], [451, 6], [452, 3], [453, 2], [454, 5], [455, 8], [456, 2]
, [457, 1], [458, 9], [459, 2], [460, 0], [461, 6], [462, 0], [463, 9], [464, 10
], [465, 4], [466, 8], [467, 8], [468, 6], [469, 4], [470, 3], [471, 5], [472, 3
], [473, 11], [474, 5], [475, 3], [476, 3], [477, 1], [478, 3], [479, 4], [480,
2], [481, 3], [482, 25], [483, 8], [484, 4], [485, 1], [486, 12], [487, 11], [48
8, 1], [489, 5], [490, 3], [491, 8], [492, 1], [493, 2], [494, 3], [495, 12], [4
96, 1], [497, 4], [498, 9], [499, 8], [500, 1]]

Pn mod nの個数を出力してみる。
（ただし、最初の３項は除く。）

n = 3 * 10 ** 6
ary0 = Array.new(n, 0)
a, b, c = 2, 0, 3
i = 2
while i < n
  a, b, c = b + c, a, b
  i += 1
  j = a % i
  ary0[j] += 1
end
p ary0[0..500].map.with_index{|n, i| [i, n]}

出力結果
[[0, 216817], [1, 6], [2, 87143], [3, 19782], [4, 12], [5, 22640], [6, 5], [7, 8
998], [8, 1], [9, 3], [10, 15929], [11, 1], [12, 7158], [13, 4], [14, 3], [15, 3
], [16, 0], [17, 6482], [18, 4], [19, 3], [20, 4], [21, 11], [22, 3005], [23, 14
], [24, 5], [25, 9], [26, 8], [27, 5], [28, 3], [29, 5510], [30, 5], [31, 2], [3
2, 3], [33, 8], [34, 8], [35, 3], [36, 4], [37, 12], [38, 4], [39, 1029], [40, 7
], [41, 6], [42, 12], [43, 7], [44, 4], [45, 8], [46, 2], [47, 7], [48, 7], [49,
 4], [50, 4], [51, 4767], [52, 9], [53, 6], [54, 2], [55, 0], [56, 2], [57, 9],
[58, 6], [59, 3], [60, 2], [61, 9], [62, 6], [63, 6], [64, 4], [65, 4], [66, 6],
 [67, 16], [68, 4501], [69, 7], [70, 4], [71, 6], [72, 2], [73, 5], [74, 10], [7
5, 9], [76, 3], [77, 11], [78, 4], [79, 9], [80, 5], [81, 5], [82, 5], [83, 8],
[84, 2], [85, 10], [86, 9], [87, 0], [88, 3], [89, 3], [90, 8498], [91, 6], [92,
 3], [93, 11], [94, 3], [95, 5], [96, 1], [97, 11], [98, 3], [99, 7], [100, 5],
[101, 15], [102, 4], [103, 4], [104, 6], [105, 7], [106, 10], [107, 10], [108, 4
], [109, 7], [110, 6], [111, 2], [112, 2], [113, 10], [114, 8], [115, 9], [116,
4], [117, 4], [118, 4], [119, 1031], [120, 12], [121, 3], [122, 15], [123, 5], [
124, 8], [125, 13], [126, 2], [127, 5], [128, 3], [129, 6], [130, 6], [131, 14],
 [132, 4], [133, 14], [134, 2], [135, 8], [136, 2], [137, 3], [138, 11], [139, 5
], [140, 5], [141, 5], [142, 3], [143, 2], [144, 6], [145, 2], [146, 4], [147, 3
], [148, 3], [149, 9], [150, 8], [151, 3], [152, 1], [153, 1], [154, 13], [155,
4], [156, 5], [157, 15], [158, 1905], [159, 5], [160, 3], [161, 4], [162, 4], [1
63, 3], [164, 2], [165, 26], [166, 7], [167, 7], [168, 3], [169, 11], [170, 9],
[171, 5], [172, 3], [173, 10], [174, 11], [175, 3], [176, 3], [177, 6], [178, 5]
, [179, 5], [180, 2], [181, 13], [182, 16], [183, 12], [184, 2], [185, 5], [186,
 10], [187, 9], [188, 4], [189, 3], [190, 3], [191, 4], [192, 3], [193, 3], [194
, 6], [195, 16], [196, 5], [197, 9], [198, 0], [199, 3], [200, 4], [201, 12], [2
02, 5], [203, 4], [204, 1], [205, 7], [206, 2], [207, 7], [208, 5], [209, 1820],
 [210, 16], [211, 1], [212, 2], [213, 7], [214, 7], [215, 3], [216, 3], [217, 3]
, [218, 14], [219, 5], [220, 2], [221, 7], [222, 8], [223, 4], [224, 6], [225, 9
], [226, 0], [227, 6], [228, 3], [229, 16], [230, 7], [231, 3], [232, 4], [233,
4], [234, 6], [235, 4], [236, 4], [237, 4], [238, 2], [239, 17], [240, 2], [241,
 4], [242, 6], [243, 5], [244, 6], [245, 14], [246, 3], [247, 6], [248, 2], [249
, 4], [250, 12], [251, 3], [252, 4], [253, 9], [254, 8], [255, 8], [256, 3], [25
7, 7], [258, 5], [259, 9], [260, 4], [261, 7], [262, 3], [263, 8], [264, 5], [26
5, 9], [266, 5], [267, 5], [268, 5], [269, 7], [270, 1], [271, 7], [272, 0], [27
3, 7], [274, 4], [275, 7], [276, 4], [277, 6919], [278, 2], [279, 13], [280, 4],
 [281, 7], [282, 12], [283, 4], [284, 2], [285, 9], [286, 4], [287, 4], [288, 3]
, [289, 3], [290, 7], [291, 4], [292, 5], [293, 18], [294, 1], [295, 5], [296, 4
], [297, 2], [298, 5], [299, 4], [300, 7], [301, 5], [302, 5], [303, 2], [304, 2
], [305, 12], [306, 1], [307, 6], [308, 5], [309, 20], [310, 2], [311, 4], [312,
 7], [313, 11], [314, 10], [315, 4], [316, 7], [317, 15], [318, 7], [319, 4], [3
20, 8], [321, 2], [322, 9], [323, 2], [324, 0], [325, 9], [326, 3], [327, 7], [3
28, 3], [329, 7], [330, 9], [331, 6], [332, 3], [333, 3], [334, 9], [335, 2], [3
36, 1], [337, 7], [338, 5], [339, 2], [340, 1], [341, 7], [342, 13], [343, 2], [
344, 5], [345, 3], [346, 15], [347, 8], [348, 3], [349, 8], [350, 7], [351, 6],
[352, 4], [353, 1], [354, 8], [355, 14], [356, 7], [357, 12], [358, 3], [359, 4]
, [360, 5], [361, 2], [362, 13], [363, 9], [364, 2], [365, 6], [366, 4], [367, 8
12], [368, 1], [369, 6], [370, 9], [371, 3], [372, 4], [373, 6], [374, 8], [375,
 5], [376, 6], [377, 5], [378, 11], [379, 3], [380, 5], [381, 11], [382, 5], [38
3, 4], [384, 5], [385, 6], [386, 4], [387, 9], [388, 4], [389, 9], [390, 6], [39
1, 2], [392, 5], [393, 4], [394, 3], [395, 7], [396, 3], [397, 6], [398, 9], [39
9, 5], [400, 4], [401, 5], [402, 7], [403, 8], [404, 7], [405, 13], [406, 2], [4
07, 8], [408, 5], [409, 4], [410, 8], [411, 8], [412, 5], [413, 5], [414, 3], [4
15, 5], [416, 8], [417, 10], [418, 6], [419, 4], [420, 2], [421, 13], [422, 6],
[423, 2], [424, 2], [425, 6], [426, 6], [427, 1], [428, 4], [429, 5], [430, 9],
[431, 1], [432, 3], [433, 3], [434, 11], [435, 8], [436, 3], [437, 9], [438, 1],
 [439, 3], [440, 2], [441, 8], [442, 7], [443, 7], [444, 5], [445, 5], [446, 3],
 [447, 4], [448, 2], [449, 4], [450, 7], [451, 6], [452, 6], [453, 13], [454, 8]
, [455, 4], [456, 3], [457, 6], [458, 6], [459, 7], [460, 1], [461, 5], [462, 6]
, [463, 5], [464, 1], [465, 3], [466, 4], [467, 4], [468, 0], [469, 6], [470, 1]
, [471, 9], [472, 5], [473, 8], [474, 9], [475, 7], [476, 5], [477, 8], [478, 0]
, [479, 5], [480, 3], [481, 6], [482, 6], [483, 3], [484, 9], [485, 12], [486, 8
00], [487, 5], [488, 3], [489, 10], [490, 6], [491, 6], [492, 3], [493, 9], [494
, 10], [495, 5], [496, 2], [497, 8], [498, 8], [499, 2], [500, 6]]

Mn mod nの個数を出力してみる。
（ただし、最初の５項は除く。）

n = 3 * 10 ** 6
ary0 = Array.new(n, 0)
ary1 = Array.new(n, 0)
a, b, c, d, e = 11, -7, 3, -1, 5
i = 4
while i < n
  a, b, c, d, e = -a + b - c + e, a, b, c, d
  i += 1
  j = a % i
  ary0[j] += 1
  ary1[i - 1 - j] += 1
end
p ary0[0..1001].map.with_index{|n, i| [i, n]}
p ary1[0..1001].map.with_index{|n, i| [-(i + 1), n]}

出力結果
[[0, 11], [1, 6], [2, 15], [3, 57081], [4, 3], [5, 8], [6, 10], [7, 3], [8, 10],
 [9, 3], [10, 8], [11, 20055], [12, 6], [13, 2], [14, 10], [15, 13], [16, 3], [1
7, 6], [18, 9], [19, 4], [20, 8], [21, 0], [22, 3], [23, 7], [24, 9], [25, 7], [
26, 10], [27, 6], [28, 6], [29, 6], [30, 8], [31, 7], [32, 8], [33, 10376], [34,
 12], [35, 10], [36, 7], [37, 8], [38, 13], [39, 6], [40, 4], [41, 6], [42, 16],
 [43, 9], [44, 11], [45, 4], [46, 6], [47, 8], [48, 4], [49, 6], [50, 2], [51, 2
2], [52, 2], [53, 7], [54, 8], [55, 6], [56, 13], [57, 12], [58, 5], [59, 14], [
60, 8], [61, 5], [62, 8], [63, 11], [64, 4], [65, 17], [66, 9], [67, 5], [68, 10
], [69, 9], [70, 6], [71, 6], [72, 7], [73, 12], [74, 7], [75, 9], [76, 2], [77,
 8], [78, 16], [79, 3], [80, 3], [81, 6], [82, 7], [83, 7], [84, 6], [85, 5], [8
6, 13], [87, 11], [88, 5], [89, 5], [90, 5], [91, 5], [92, 8], [93, 8], [94, 2],
 [95, 6], [96, 16], [97, 4], [98, 4], [99, 10622], [100, 2], [101, 10], [102, 8]
, [103, 8], [104, 6], [105, 4], [106, 4], [107, 6], [108, 11], [109, 7], [110, 1
5], [111, 6], [112, 3], [113, 9], [114, 17], [115, 5], [116, 6], [117, 8], [118,
 3], [119, 7], [120, 7], [121, 4], [122, 7], [123, 6], [124, 3], [125, 5], [126,
 9], [127, 5], [128, 8], [129, 15], [130, 3], [131, 8], [132, 8], [133, 4], [134
, 8], [135, 6], [136, 6], [137, 8], [138, 7], [139, 5], [140, 6], [141, 10], [14
2, 4], [143, 8], [144, 7], [145, 3], [146, 15], [147, 4], [148, 8], [149, 6], [1
50, 13], [151, 3], [152, 6], [153, 9], [154, 10], [155, 15], [156, 4], [157, 2],
 [158, 4], [159, 9], [160, 1], [161, 9], [162, 7], [163, 8], [164, 9], [165, 4],
 [166, 6], [167, 3], [168, 13], [169, 5], [170, 7], [171, 5], [172, 6], [173, 14
], [174, 4], [175, 6], [176, 7], [177, 16], [178, 2], [179, 15], [180, 5], [181,
 2], [182, 18], [183, 8], [184, 10], [185, 7], [186, 6], [187, 7], [188, 14], [1
89, 3], [190, 7], [191, 12], [192, 7], [193, 9], [194, 13], [195, 17], [196, 3],
 [197, 6], [198, 11], [199, 0], [200, 7], [201, 3], [202, 5], [203, 10], [204, 8
], [205, 5], [206, 7], [207, 4], [208, 5], [209, 8], [210, 6], [211, 6], [212, 6
], [213, 8], [214, 6], [215, 5], [216, 2], [217, 4], [218, 16], [219, 6], [220,
2], [221, 7], [222, 10], [223, 7], [224, 6], [225, 5], [226, 5], [227, 26], [228
, 9], [229, 1], [230, 7], [231, 13], [232, 5], [233, 9], [234, 5], [235, 4], [23
6, 8], [237, 5], [238, 9], [239, 6], [240, 6], [241, 4], [242, 7], [243, 14], [2
44, 2], [245, 5], [246, 9], [247, 3], [248, 8], [249, 7], [250, 4], [251, 13], [
252, 6], [253, 3], [254, 12], [255, 5], [256, 4], [257, 9], [258, 26], [259, 3],
 [260, 10], [261, 5], [262, 3], [263, 4], [264, 4], [265, 4], [266, 7], [267, 13
], [268, 4], [269, 8], [270, 10], [271, 4], [272, 7], [273, 6], [274, 12], [275,
 9], [276, 7], [277, 6], [278, 6], [279, 4], [280, 10], [281, 12], [282, 10], [2
83, 6], [284, 7], [285, 8], [286, 3], [287, 8], [288, 5], [289, 3], [290, 14], [
291, 9], [292, 6], [293, 6], [294, 9], [295, 2], [296, 5], [297, 4], [298, 5], [
299, 10], [300, 9], [301, 4], [302, 6], [303, 6], [304, 6], [305, 5], [306, 8],
[307, 5], [308, 13], [309, 4], [310, 5], [311, 4], [312, 12], [313, 7], [314, 5]
, [315, 4], [316, 3], [317, 8], [318, 6491], [319, 4], [320, 8], [321, 6], [322,
 6], [323, 9], [324, 3], [325, 3], [326, 8], [327, 8], [328, 3], [329, 9], [330,
 9], [331, 4], [332, 9], [333, 6], [334, 8], [335, 15], [336, 6], [337, 5], [338
, 6], [339, 16], [340, 4], [341, 3], [342, 4], [343, 2], [344, 11], [345, 2], [3
46, 1], [347, 8], [348, 8], [349, 3], [350, 4], [351, 7], [352, 3], [353, 17], [
354, 7], [355, 2], [356, 5], [357, 11], [358, 4], [359, 10], [360, 7], [361, 3],
 [362, 8], [363, 4], [364, 3], [365, 5], [366, 21], [367, 3], [368, 10], [369, 4
], [370, 3], [371, 9], [372, 12], [373, 5], [374, 4], [375, 6], [376, 6], [377,
5], [378, 6], [379, 4], [380, 8], [381, 2], [382, 5], [383, 2], [384, 12], [385,
 2], [386, 8], [387, 3], [388, 3], [389, 12], [390, 4], [391, 4], [392, 7], [393
, 11], [394, 5], [395, 9], [396, 4], [397, 5], [398, 13], [399, 10], [400, 2], [
401, 8], [402, 11], [403, 5], [404, 7], [405, 4], [406, 4], [407, 9], [408, 5],
[409, 5], [410, 5], [411, 8], [412, 1], [413, 4], [414, 3], [415, 4], [416, 10],
 [417, 4], [418, 4], [419, 6], [420, 8], [421, 2], [422, 5], [423, 6], [424, 5],
 [425, 6], [426, 5], [427, 2], [428, 8], [429, 4], [430, 3], [431, 7], [432, 6],
 [433, 7], [434, 11], [435, 6], [436, 4], [437, 6], [438, 7], [439, 4], [440, 5]
, [441, 3], [442, 6], [443, 20], [444, 5], [445, 2], [446, 5], [447, 9], [448, 8
], [449, 9], [450, 13], [451, 4], [452, 5], [453, 10], [454, 6], [455, 4], [456,
 11], [457, 4], [458, 7], [459, 12], [460, 7], [461, 14], [462, 5], [463, 3], [4
64, 16], [465, 7], [466, 7], [467, 15], [468, 5], [469, 9], [470, 12], [471, 4],
 [472, 3], [473, 6], [474, 5], [475, 2], [476, 2], [477, 1], [478, 4], [479, 7],
 [480, 3], [481, 6], [482, 11], [483, 17], [484, 1], [485, 3], [486, 8], [487, 2
], [488, 10], [489, 8], [490, 5], [491, 8], [492, 5], [493, 3], [494, 18], [495,
 6], [496, 3], [497, 8], [498, 8], [499, 16], [500, 6], [501, 16], [502, 5], [50
3, 6], [504, 5], [505, 2], [506, 10], [507, 6], [508, 3], [509, 2], [510, 8], [5
11, 1], [512, 4], [513, 9], [514, 7], [515, 12], [516, 4], [517, 6], [518, 9], [
519, 7], [520, 8], [521, 5], [522, 3], [523, 7], [524, 4], [525, 1], [526, 7], [
527, 6], [528, 6], [529, 1], [530, 7], [531, 4], [532, 1], [533, 11], [534, 8],
[535, 6], [536, 10], [537, 4], [538, 9], [539, 6], [540, 8], [541, 3], [542, 9],
 [543, 3], [544, 0], [545, 14], [546, 11], [547, 2], [548, 4], [549, 5], [550, 3
], [551, 13], [552, 4], [553, 4], [554, 7], [555, 17], [556, 3], [557, 7], [558,
 4], [559, 3], [560, 7], [561, 9], [562, 4], [563, 13], [564, 9], [565, 1], [566
, 9], [567, 7], [568, 3], [569, 4], [570, 6], [571, 4], [572, 12], [573, 12], [5
74, 9], [575, 2], [576, 6], [577, 3], [578, 12], [579, 11], [580, 5], [581, 5],
[582, 16], [583, 3], [584, 7], [585, 6], [586, 3], [587, 10], [588, 9], [589, 3]
, [590, 8], [591, 11], [592, 6], [593, 5], [594, 8], [595, 5], [596, 4], [597, 5
], [598, 4], [599, 7], [600, 8], [601, 5], [602, 5], [603, 10], [604, 5], [605,
5], [606, 11], [607, 2], [608, 10], [609, 20], [610, 6], [611, 8], [612, 8], [61
3, 6], [614, 4], [615, 3], [616, 2], [617, 7], [618, 10], [619, 5], [620, 4], [6
21, 2], [622, 6], [623, 4], [624, 4], [625, 5], [626, 8], [627, 13], [628, 6], [
629, 4], [630, 7], [631, 0], [632, 11], [633, 12], [634, 5], [635, 8], [636, 14]
, [637, 2], [638, 7], [639, 2], [640, 7], [641, 12], [642, 2], [643, 11], [644,
3], [645, 7], [646, 3], [647, 4], [648, 5], [649, 4], [650, 6], [651, 2], [652,
8], [653, 8], [654, 6], [655, 1], [656, 7], [657, 8], [658, 6], [659, 10], [660,
 2], [661, 5], [662, 5], [663, 20], [664, 8], [665, 1], [666, 3], [667, 6], [668
, 7], [669, 2], [670, 3], [671, 5], [672, 6], [673, 9], [674, 7], [675, 8], [676
, 5], [677, 11], [678, 5], [679, 3], [680, 11], [681, 6], [682, 3], [683, 9], [6
84, 5], [685, 1], [686, 17], [687, 5], [688, 5], [689, 2], [690, 7], [691, 9], [
692, 8], [693, 8], [694, 5], [695, 13], [696, 8], [697, 2], [698, 13], [699, 10]
, [700, 3], [701, 5], [702, 5], [703, 3], [704, 5], [705, 7], [706, 8], [707, 13
], [708, 10], [709, 8], [710, 1], [711, 3], [712, 3], [713, 14], [714, 2], [715,
 3], [716, 5], [717, 6], [718, 6], [719, 2], [720, 9], [721, 5], [722, 9], [723,
 10], [724, 2], [725, 9], [726, 8], [727, 0], [728, 7], [729, 3], [730, 1], [731
, 15], [732, 7], [733, 5], [734, 11], [735, 10], [736, 5], [737, 3], [738, 12],
[739, 4], [740, 7], [741, 4], [742, 10], [743, 7], [744, 12], [745, 0], [746, 7]
, [747, 6], [748, 1], [749, 4], [750, 6], [751, 8], [752, 4], [753, 10], [754, 5
], [755, 9], [756, 3], [757, 3], [758, 15], [759, 7], [760, 9], [761, 9], [762,
8], [763, 3], [764, 6], [765, 2], [766, 4], [767, 10], [768, 7], [769, 2], [770,
 9], [771, 9], [772, 3], [773, 7], [774, 5], [775, 4], [776, 13], [777, 5], [778
, 6], [779, 8], [780, 4], [781, 2], [782, 5], [783, 4], [784, 1], [785, 7], [786
, 10], [787, 3], [788, 5], [789, 7], [790, 5], [791, 5], [792, 2], [793, 10], [7
94, 9], [795, 4], [796, 3], [797, 4], [798, 10], [799, 1], [800, 3], [801, 6], [
802, 2], [803, 6], [804, 4], [805, 9], [806, 4], [807, 12], [808, 4], [809, 5],
[810, 5], [811, 3], [812, 6], [813, 13], [814, 7], [815, 1], [816, 5], [817, 3],
 [818, 11], [819, 12], [820, 4], [821, 12], [822, 7], [823, 5], [824, 9], [825,
6], [826, 4], [827, 10], [828, 6], [829, 2], [830, 8], [831, 9], [832, 7], [833,
 10], [834, 12], [835, 8], [836, 5], [837, 2], [838, 6], [839, 4], [840, 3], [84
1, 3], [842, 4], [843, 9], [844, 0], [845, 4], [846, 6], [847, 1], [848, 9], [84
9, 12], [850, 6], [851, 9], [852, 9], [853, 3], [854, 5], [855, 5], [856, 8], [8
57, 7], [858, 6], [859, 5], [860, 6], [861, 8], [862, 6], [863, 8], [864, 2], [8
65, 4], [866, 6], [867, 4], [868, 1], [869, 5], [870, 10], [871, 1], [872, 9], [
873, 1], [874, 2], [875, 12], [876, 7], [877, 0], [878, 5], [879, 4], [880, 3],
[881, 6], [882, 7], [883, 5], [884, 5], [885, 6], [886, 5], [887, 3], [888, 8],
[889, 3], [890, 5], [891, 2], [892, 4], [893, 9], [894, 3], [895, 3], [896, 3],
[897, 7], [898, 4], [899, 7], [900, 1], [901, 3], [902, 15], [903, 3], [904, 6],
 [905, 4], [906, 11], [907, 6], [908, 7], [909, 4], [910, 4], [911, 6], [912, 7]
, [913, 6], [914, 9], [915, 15], [916, 3], [917, 3], [918, 10], [919, 2], [920,
9], [921, 4], [922, 4], [923, 8], [924, 7], [925, 6], [926, 8], [927, 5], [928,
5], [929, 9], [930, 5], [931, 5], [932, 6], [933, 12], [934, 8], [935, 1], [936,
 5], [937, 5], [938, 5], [939, 8], [940, 4], [941, 6], [942, 9], [943, 7], [944,
 5], [945, 3], [946, 2], [947, 7], [948, 5], [949, 3], [950, 3], [951, 10], [952
, 5], [953, 6], [954, 3], [955, 3], [956, 11], [957, 4], [958, 2], [959, 3], [96
0, 6], [961, 3], [962, 2], [963, 13], [964, 3], [965, 5], [966, 5], [967, 1], [9
68, 8], [969, 8], [970, 2], [971, 10], [972, 10], [973, 3], [974, 9], [975, 4],
[976, 2], [977, 7], [978, 9], [979, 5], [980, 1], [981, 4], [982, 4], [983, 12],
 [984, 11], [985, 2], [986, 10], [987, 16], [988, 3], [989, 12], [990, 9], [991,
 0], [992, 5], [993, 8], [994, 6], [995, 8], [996, 6], [997, 1], [998, 7], [999,
 5], [1000, 5], [1001, 1847]]
[[-1, 216814], [-2, 6], [-3, 5], [-4, 2], [-5, 4], [-6, 3], [-7, 39210], [-8, 10
], [-9, 2], [-10, 5], [-11, 4], [-12, 11], [-13, 10], [-14, 7], [-15, 5], [-16,
12237], [-17, 4], [-18, 13], [-19, 4], [-20, 1], [-21, 9], [-22, 8], [-23, 6], [
-24, 6], [-25, 7], [-26, 4], [-27, 9], [-28, 9], [-29, 5], [-30, 6], [-31, 9], [
-32, 2], [-33, 2], [-34, 7], [-35, 3], [-36, 7], [-37, 5], [-38, 6], [-39, 11],
[-40, 5], [-41, 8], [-42, 8], [-43, 14], [-44, 8], [-45, 11], [-46, 9], [-47, 12
], [-48, 5], [-49, 8], [-50, 5], [-51, 5], [-52, 9], [-53, 3], [-54, 4], [-55, 5
], [-56, 6], [-57, 4707], [-58, 6], [-59, 4], [-60, 5], [-61, 22], [-62, 7], [-6
3, 10], [-64, 3], [-65, 7], [-66, 15], [-67, 8], [-68, 3], [-69, 5], [-70, 12],
[-71, 6], [-72, 6], [-73, 3], [-74, 4], [-75, 10], [-76, 6], [-77, 4], [-78, 8],
 [-79, 12], [-80, 2], [-81, 2], [-82, 6], [-83, 2], [-84, 7], [-85, 7], [-86, 6]
, [-87, 6], [-88, 8], [-89, 7], [-90, 14], [-91, 11], [-92, 4], [-93, 18], [-94,
 9], [-95, 6], [-96, 6], [-97, 12], [-98, 5], [-99, 9], [-100, 9], [-101, 9], [-
102, 8], [-103, 8], [-104, 3], [-105, 9], [-106, 10], [-107, 3], [-108, 3], [-10
9, 9], [-110, 5], [-111, 4], [-112, 8], [-113, 6], [-114, 3], [-115, 10], [-116,
 0], [-117, 6], [-118, 3], [-119, 4], [-120, 13], [-121, 7], [-122, 4], [-123, 8
], [-124, 14], [-125, 6], [-126, 14], [-127, 6], [-128, 4], [-129, 11], [-130, 8
], [-131, 1], [-132, 3], [-133, 12], [-134, 4], [-135, 6], [-136, 10], [-137, 1]
, [-138, 10], [-139, 9], [-140, 1], [-141, 13], [-142, 8], [-143, 5], [-144, 5],
 [-145, 8], [-146, 8], [-147, 18], [-148, 7], [-149, 9], [-150, 11], [-151, 7],
[-152, 1], [-153, 5], [-154, 5], [-155, 8], [-156, 8], [-157, 15], [-158, 4], [-
159, 8], [-160, 11], [-161, 3], [-162, 5], [-163, 5], [-164, 0], [-165, 10], [-1
66, 9], [-167, 5], [-168, 8], [-169, 11], [-170, 4], [-171, 7], [-172, 7], [-173
, 10], [-174, 17], [-175, 8], [-176, 0], [-177, 7], [-178, 14320], [-179, 2], [-
180, 3], [-181, 9], [-182, 15], [-183, 2], [-184, 6], [-185, 1], [-186, 2], [-18
7, 8], [-188, 7], [-189, 12], [-190, 8], [-191, 12], [-192, 9], [-193, 7], [-194
, 3], [-195, 5], [-196, 3], [-197, 8], [-198, 4], [-199, 8], [-200, 4], [-201, 6
], [-202, 9], [-203, 3], [-204, 7], [-205, 16], [-206, 2], [-207, 2], [-208, 7],
 [-209, 4], [-210, 7], [-211, 7], [-212, 3], [-213, 5], [-214, 12], [-215, 5], [
-216, 6], [-217, 3], [-218, 2], [-219, 7], [-220, 3], [-221, 12], [-222, 7], [-2
23, 9], [-224, 5], [-225, 5], [-226, 7], [-227, 1], [-228, 20], [-229, 4], [-230
, 0], [-231, 3], [-232, 11], [-233, 4], [-234, 6], [-235, 3], [-236, 4], [-237,
18], [-238, 12], [-239, 4], [-240, 4], [-241, 12], [-242, 6], [-243, 8], [-244,
5], [-245, 5], [-246, 10], [-247, 9], [-248, 5], [-249, 10], [-250, 7], [-251, 8
], [-252, 6], [-253, 13], [-254, 8], [-255, 16], [-256, 5], [-257, 4], [-258, 5]
, [-259, 16], [-260, 3], [-261, 7], [-262, 9], [-263, 4], [-264, 14], [-265, 8],
 [-266, 4], [-267, 10], [-268, 11], [-269, 5], [-270, 7], [-271, 10], [-272, 5],
 [-273, 9], [-274, 6], [-275, 6], [-276, 4], [-277, 9], [-278, 3], [-279, 4], [-
280, 5], [-281, 1], [-282, 19], [-283, 4], [-284, 3], [-285, 8], [-286, 7], [-28
7, 8], [-288, 6], [-289, 2], [-290, 4], [-291, 2], [-292, 12], [-293, 6], [-294,
 6], [-295, 14], [-296, 4], [-297, 5], [-298, 3], [-299, 2], [-300, 6], [-301, 1
0], [-302, 6], [-303, 5], [-304, 12], [-305, 4], [-306, 7], [-307, 10], [-308, 5
], [-309, 12], [-310, 5], [-311, 6], [-312, 11], [-313, 4], [-314, 2], [-315, 6]
, [-316, 0], [-317, 3], [-318, 13], [-319, 6], [-320, 11], [-321, 4], [-322, 7],
 [-323, 4], [-324, 5], [-325, 4], [-326, 3], [-327, 7], [-328, 8], [-329, 2], [-
330, 4], [-331, 2], [-332, 3], [-333, 6], [-334, 9], [-335, 7], [-336, 5], [-337
, 9], [-338, 5], [-339, 5], [-340, 2], [-341, 2], [-342, 1], [-343, 4], [-344, 4
], [-345, 9], [-346, 7], [-347, 4], [-348, 1], [-349, 10], [-350, 10], [-351, 6]
, [-352, 3], [-353, 2], [-354, 13], [-355, 3], [-356, 2], [-357, 3], [-358, 6],
[-359, 4], [-360, 5], [-361, 5], [-362, 6], [-363, 10], [-364, 6], [-365, 6], [-
366, 11], [-367, 16], [-368, 4], [-369, 5], [-370, 14], [-371, 2], [-372, 5], [-
373, 11], [-374, 5], [-375, 6], [-376, 10], [-377, 1], [-378, 9], [-379, 4], [-3
80, 3], [-381, 7], [-382, 10], [-383, 4], [-384, 2], [-385, 6], [-386, 2], [-387
, 5], [-388, 2], [-389, 3], [-390, 8], [-391, 6], [-392, 6], [-393, 5], [-394, 5
], [-395, 2], [-396, 5], [-397, 11], [-398, 8], [-399, 5], [-400, 10], [-401, 4]
, [-402, 6], [-403, 6], [-404, 2], [-405, 6], [-406, 8], [-407, 3], [-408, 9], [
-409, 5], [-410, 2], [-411, 5], [-412, 6], [-413, 2], [-414, 5], [-415, 9], [-41
6, 7], [-417, 12], [-418, 11], [-419, 2], [-420, 3], [-421, 15], [-422, 8], [-42
3, 2], [-424, 6], [-425, 9], [-426, 5], [-427, 9], [-428, 1], [-429, 5], [-430,
10], [-431, 7], [-432, 7], [-433, 3], [-434, 3], [-435, 7], [-436, 2], [-437, 2]
, [-438, 8], [-439, 6], [-440, 1], [-441, 2], [-442, 5], [-443, 2], [-444, 6], [
-445, 9], [-446, 4], [-447, 7], [-448, 9], [-449, 5], [-450, 7], [-451, 4], [-45
2, 3], [-453, 9], [-454, 8], [-455, 3], [-456, 5], [-457, 9], [-458, 10], [-459,
 8], [-460, 4], [-461, 7], [-462, 9], [-463, 3], [-464, 3], [-465, 2], [-466, 15
], [-467, 2], [-468, 7], [-469, 1], [-470, 3], [-471, 12], [-472, 11], [-473, 2]
, [-474, 8], [-475, 13], [-476, 3], [-477, 11], [-478, 6], [-479, 4], [-480, 10]
, [-481, 7], [-482, 7], [-483, 5], [-484, 6], [-485, 2], [-486, 2], [-487, 12],
[-488, 5], [-489, 7], [-490, 7], [-491, 5], [-492, 6], [-493, 21], [-494, 2], [-
495, 6], [-496, 2], [-497, 4], [-498, 20], [-499, 7], [-500, 4], [-501, 9], [-50
2, 26], [-503, 0], [-504, 3], [-505, 6], [-506, 2], [-507, 13], [-508, 5], [-509
, 4], [-510, 4], [-511, 9], [-512, 4], [-513, 6], [-514, 8], [-515, 4], [-516, 8
], [-517, 2], [-518, 1], [-519, 5], [-520, 12], [-521, 0], [-522, 7], [-523, 4],
 [-524, 3], [-525, 21], [-526, 2], [-527, 5], [-528, 5], [-529, 8], [-530, 4], [
-531, 7], [-532, 3], [-533, 4], [-534, 5], [-535, 6], [-536, 9], [-537, 4], [-53
8, 13], [-539, 3], [-540, 5], [-541, 7], [-542, 5], [-543, 8], [-544, 9], [-545,
 1], [-546, 5], [-547, 14], [-548, 1], [-549, 7], [-550, 5], [-551, 2], [-552, 8
], [-553, 3], [-554, 5], [-555, 2], [-556, 6], [-557, 2], [-558, 5], [-559, 7],
[-560, 2], [-561, 5], [-562, 2102], [-563, 2], [-564, 6], [-565, 10], [-566, 2],
 [-567, 5], [-568, 8], [-569, 6], [-570, 6], [-571, 8], [-572, 7], [-573, 8], [-
574, 19], [-575, 2], [-576, 4], [-577, 7], [-578, 4], [-579, 9], [-580, 3], [-58
1, 4], [-582, 5], [-583, 6], [-584, 3], [-585, 6], [-586, 4], [-587, 5], [-588,
7], [-589, 19], [-590, 4], [-591, 3], [-592, 6], [-593, 4], [-594, 2], [-595, 2]
, [-596, 2], [-597, 9], [-598, 9], [-599, 0], [-600, 10], [-601, 7], [-602, 2],
[-603, 9], [-604, 7], [-605, 4], [-606, 10], [-607, 7], [-608, 3], [-609, 7], [-
610, 7], [-611, 2], [-612, 5], [-613, 8], [-614, 7], [-615, 12], [-616, 9], [-61
7, 6], [-618, 8], [-619, 10], [-620, 3], [-621, 5], [-622, 7], [-623, 2], [-624,
 4], [-625, 2], [-626, 3], [-627, 3], [-628, 6], [-629, 6], [-630, 5], [-631, 8]
, [-632, 1], [-633, 10], [-634, 9], [-635, 5], [-636, 10], [-637, 9], [-638, 2],
 [-639, 6], [-640, 7], [-641, 7], [-642, 9], [-643, 4], [-644, 4], [-645, 3], [-
646, 4], [-647, 6], [-648, 6], [-649, 6], [-650, 5], [-651, 6], [-652, 4], [-653
, 4], [-654, 7], [-655, 4], [-656, 1], [-657, 6], [-658, 7], [-659, 2], [-660, 6
], [-661, 1], [-662, 6], [-663, 7], [-664, 12], [-665, 2], [-666, 12], [-667, 6]
, [-668, 4], [-669, 9], [-670, 10], [-671, 6], [-672, 6], [-673, 4], [-674, 8],
[-675, 11], [-676, 0], [-677, 9], [-678, 5], [-679, 4], [-680, 1], [-681, 3], [-
682, 14], [-683, 2], [-684, 5], [-685, 3], [-686, 2], [-687, 8], [-688, 3], [-68
9, 6], [-690, 8], [-691, 9], [-692, 1], [-693, 3], [-694, 5], [-695, 2], [-696,
9], [-697, 12], [-698, 3], [-699, 2], [-700, 8], [-701, 14], [-702, 7], [-703, 7
], [-704, 0], [-705, 6], [-706, 7], [-707, 5], [-708, 6], [-709, 12], [-710, 2],
 [-711, 1], [-712, 6], [-713, 4], [-714, 16], [-715, 6], [-716, 0], [-717, 7], [
-718, 15], [-719, 6], [-720, 7], [-721, 6], [-722, 9], [-723, 5], [-724, 6], [-7
25, 6], [-726, 5], [-727, 10], [-728, 5], [-729, 7], [-730, 6], [-731, 5], [-732
, 6], [-733, 10], [-734, 2], [-735, 5], [-736, 11], [-737, 1], [-738, 8], [-739,
 4], [-740, 4], [-741, 13], [-742, 4], [-743, 7], [-744, 7], [-745, 9], [-746, 3
], [-747, 6], [-748, 6], [-749, 6], [-750, 6], [-751, 11], [-752, 8], [-753, 5],
 [-754, 11], [-755, 4], [-756, 3], [-757, 7], [-758, 1], [-759, 11], [-760, 7],
[-761, 5], [-762, 8], [-763, 8], [-764, 3], [-765, 6], [-766, 5], [-767, 6], [-7
68, 10], [-769, 3], [-770, 5], [-771, 6], [-772, 13], [-773, 1], [-774, 4], [-77
5, 9], [-776, 11], [-777, 7], [-778, 4], [-779, 3], [-780, 3], [-781, 12], [-782
, 7], [-783, 8], [-784, 5], [-785, 5], [-786, 14], [-787, 8], [-788, 5], [-789,
6], [-790, 4], [-791, 9], [-792, 8], [-793, 2], [-794, 3], [-795, 10], [-796, 4]
, [-797, 3], [-798, 3], [-799, 15], [-800, 1], [-801, 3], [-802, 12], [-803, 4],
 [-804, 2], [-805, 8], [-806, 4], [-807, 11], [-808, 6], [-809, 4], [-810, 4], [
-811, 5], [-812, 6], [-813, 7], [-814, 4], [-815, 10], [-816, 4], [-817, 4], [-8
18, 9], [-819, 4], [-820, 2], [-821, 5], [-822, 8], [-823, 6], [-824, 7], [-825,
 3], [-826, 15], [-827, 1], [-828, 6], [-829, 12], [-830, 4], [-831, 9], [-832,
11], [-833, 8], [-834, 3], [-835, 8], [-836, 2], [-837, 7], [-838, 3], [-839, 4]
, [-840, 7], [-841, 3], [-842, 6], [-843, 8], [-844, 7], [-845, 3], [-846, 7], [
-847, 7], [-848, 2], [-849, 10], [-850, 11], [-851, 2], [-852, 2], [-853, 10], [
-854, 3], [-855, 2], [-856, 5], [-857, 1], [-858, 2], [-859, 8], [-860, 6], [-86
1, 6], [-862, 10], [-863, 2], [-864, 7], [-865, 5], [-866, 8], [-867, 8], [-868,
 3], [-869, 2], [-870, 3], [-871, 10], [-872, 2], [-873, 5], [-874, 7], [-875, 1
], [-876, 5], [-877, 11], [-878, 3], [-879, 3], [-880, 6], [-881, 1], [-882, 10]
, [-883, 7], [-884, 2], [-885, 8], [-886, 9], [-887, 2], [-888, 2], [-889, 7], [
-890, 3], [-891, 5], [-892, 6], [-893, 7], [-894, 11], [-895, 3], [-896, 6], [-8
97, 5], [-898, 9], [-899, 2], [-900, 3], [-901, 8], [-902, 5], [-903, 11], [-904
, 11], [-905, 4], [-906, 5], [-907, 14], [-908, 2], [-909, 9], [-910, 2], [-911,
 2], [-912, 10], [-913, 4], [-914, 7], [-915, 2], [-916, 5], [-917, 3], [-918, 5
], [-919, 2], [-920, 3], [-921, 7], [-922, 9], [-923, 1], [-924, 1], [-925, 8],
[-926, 4], [-927, 6], [-928, 5], [-929, 2], [-930, 9], [-931, 5], [-932, 3], [-9
33, 7], [-934, 11], [-935, 1], [-936, 10], [-937, 7], [-938, 3], [-939, 11], [-9
40, 5], [-941, 10], [-942, 6], [-943, 14], [-944, 4], [-945, 7], [-946, 8], [-94
7, 4], [-948, 5], [-949, 12], [-950, 2], [-951, 4], [-952, 6], [-953, 3], [-954,
 4], [-955, 3], [-956, 2], [-957, 35], [-958, 4], [-959, 5], [-960, 4], [-961, 9
], [-962, 6], [-963, 5], [-964, 5], [-965, 2], [-966, 10], [-967, 13], [-968, 9]
, [-969, 4], [-970, 4], [-971, 3], [-972, 4], [-973, 5], [-974, 5], [-975, 7], [
-976, 7], [-977, 2], [-978, 5], [-979, 6], [-980, 2], [-981, 2], [-982, 8], [-98
3, 3], [-984, 6], [-985, 7], [-986, 2], [-987, 10], [-988, 7], [-989, 3], [-990,
 6], [-991, 5], [-992, 1], [-993, 4], [-994, 10], [-995, 2], [-996, 5], [-997, 9
], [-998, 2], [-999, 2], [-1000, 7], [-1001, 2], [-1002, 4]]