6.4 LDA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6.4 LDA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import re\n",
    "from nltk.corpus import stopwords\n",
    "from nltk.tokenize import word_tokenize\n",
    "from nltk.stem import PorterStemmer\n",
    "import gensim\n",
    "import gensim.corpora as corpora"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Load Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = pd.read_csv(\"news_articles.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>title</th>\n",
       "      <th>content</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>25626</td>\n",
       "      <td>One Weight-Loss Approach Fits All? No, Not Eve...</td>\n",
       "      <td>Dr. Frank Sacks, a professor of nutrition at H...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>19551</td>\n",
       "      <td>South Carolina Stuns Baylor to Reach the Round...</td>\n",
       "      <td>South Carolina’s win over   Duke was not only ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>25221</td>\n",
       "      <td>U.S. Presidential Race, Apple, Gene Wilder: Yo...</td>\n",
       "      <td>(Want to get this briefing by email? Here’s th...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>18026</td>\n",
       "      <td>His Predecessor Gone, Gambia’s New President F...</td>\n",
       "      <td>BANJUL, Gambia  —   A week after he was inaugu...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>21063</td>\n",
       "      <td>‘Harry Potter and the Cursed Child’ Goes From ...</td>\n",
       "      <td>The biggest book of the summer isn’t a blockbu...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      id                                              title  \\\n",
       "0  25626  One Weight-Loss Approach Fits All? No, Not Eve...   \n",
       "1  19551  South Carolina Stuns Baylor to Reach the Round...   \n",
       "2  25221  U.S. Presidential Race, Apple, Gene Wilder: Yo...   \n",
       "3  18026  His Predecessor Gone, Gambia’s New President F...   \n",
       "4  21063  ‘Harry Potter and the Cursed Child’ Goes From ...   \n",
       "\n",
       "                                             content  \n",
       "0  Dr. Frank Sacks, a professor of nutrition at H...  \n",
       "1  South Carolina’s win over   Duke was not only ...  \n",
       "2  (Want to get this briefing by email? Here’s th...  \n",
       "3  BANJUL, Gambia  —   A week after he was inaugu...  \n",
       "4  The biggest book of the summer isn’t a blockbu...  "
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "RangeIndex: 100 entries, 0 to 99\n",
      "Data columns (total 3 columns):\n",
      " #   Column   Non-Null Count  Dtype \n",
      "---  ------   --------------  ----- \n",
      " 0   id       100 non-null    int64 \n",
      " 1   title    100 non-null    object\n",
      " 2   content  100 non-null    object\n",
      "dtypes: int64(1), object(2)\n",
      "memory usage: 2.5+ KB\n"
     ]
    }
   ],
   "source": [
    "data.info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clean Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# take just the content of the article, lowercase and remove punctuation\n",
    "articles = data['content'].str.lower().apply(lambda x: re.sub(r\"([^\\w\\s])\", \"\", x))\n",
    "\n",
    "# stop word removal\n",
    "en_stopwords = stopwords.words('english')\n",
    "articles = articles.apply(lambda x: ' '.join([word for word in x.split() if word not in (en_stopwords)]))\n",
    "\n",
    "# tokenize\n",
    "articles = articles.apply(lambda x: word_tokenize(x))\n",
    "\n",
    "# stemming (done for speed as we have a lot of text)\n",
    "ps = PorterStemmer()\n",
    "articles = articles.apply(lambda tokens: [ps.stem(token) for token in tokens])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0     [meet, donald, j, trump, nation, tech, elit, h...\n",
       "1     [good, morn, want, get, california, today, ema...\n",
       "2     [washington, good, news, repres, mike, pompeo,...\n",
       "3     [morrison, colo, surround, geolog, format, cra...\n",
       "4     [face, might, seem, right, time, invest, turke...\n",
       "5     [lo, angel, shortli, drop, youngest, daughter,...\n",
       "6     [indianapoli, senat, ted, cruz, texa, desper, ...\n",
       "7     [cate, blanchett, prove, strong, draw, broadwa...\n",
       "8     [cleveland, monday, night, donald, j, trump, b...\n",
       "9     [good, morn, want, get, california, today, ema...\n",
       "10    [lo, angel, john, mayer, explain, he, fact, ge...\n",
       "11    [first, new, episod, presid, donald, j, trump,...\n",
       "12    [least, 27, peopl, shot, seven, fatal, period,...\n",
       "13    [tesla, motor, maverick, maker, scrutini, fede...\n",
       "14    [time, journalist, iraq, sunni, heartland, eva...\n",
       "15    [washington, presid, trump, plan, take, execut...\n",
       "16    [nomad, wander, necessari, surviv, came, stock...\n",
       "17    [st, petersburg, russia, quietli, number, russ...\n",
       "18    [jerusalem, isra, turkish, leader, announc, fo...\n",
       "19    [braulio, jatar, biggest, scoop, year, venezue...\n",
       "Name: content, dtype: object"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "articles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Vectorization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dictionary(3892 unique tokens: ['1', '2017', '2018', '3', '4']...)\n"
     ]
    }
   ],
   "source": [
    "# create dictionary of all words\n",
    "dictionary = corpora.Dictionary(articles)\n",
    "print(dictionary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# vecotize using bag of words into a document term matrix\n",
    "doc_term = [dictionary.doc2bow(text) for text in articles]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 2), (7, 1), (8, 1), (9, 1), (10, 1), (11, 1), (12, 1), (13, 1), (14, 1), (15, 4), (16, 1), (17, 1), (18, 1), (19, 1), (20, 1), (21, 1), (22, 1), (23, 1), (24, 1), (25, 5), (26, 1), (27, 1), (28, 2), (29, 1), (30, 4), (31, 1), (32, 2), (33, 1), (34, 1), (35, 1), (36, 1), (37, 3), (38, 1), (39, 1), (40, 1), (41, 3), (42, 1), (43, 1), (44, 1), (45, 3), (46, 1), (47, 1), (48, 3), (49, 1), (50, 1), (51, 1), (52, 1), (53, 1), (54, 1), (55, 1), (56, 1), (57, 2), (58, 1), (59, 2), (60, 1), (61, 2), (62, 2), (63, 1), (64, 1), (65, 1), (66, 1), (67, 1), (68, 1), (69, 3), (70, 1), (71, 2), (72, 1), (73, 1), (74, 1), (75, 1), (76, 6), (77, 1), (78, 2), (79, 1), (80, 1), (81, 3), (82, 1), (83, 1), (84, 1), (85, 1), (86, 1), (87, 2), (88, 4), (89, 1), (90, 1), (91, 2), (92, 1), (93, 1), (94, 1), (95, 1), (96, 1), (97, 3), (98, 1), (99, 1), (100, 1), (101, 1), (102, 1), (103, 1), (104, 1), (105, 2), (106, 1), (107, 1), (108, 1), (109, 1), (110, 1), (111, 1), (112, 1), (113, 1), (114, 1), (115, 2), (116, 2), (117, 2), (118, 1), (119, 1), (120, 1), (121, 1), (122, 1), (123, 1), (124, 1), (125, 1), (126, 1), (127, 1), (128, 1), (129, 1), (130, 2), (131, 1), (132, 1), (133, 1), (134, 1), (135, 1), (136, 1), (137, 12), (138, 1), (139, 1), (140, 1), (141, 1), (142, 1), (143, 1), (144, 1), (145, 1), (146, 1), (147, 1), (148, 1), (149, 1), (150, 1), (151, 1), (152, 1), (153, 1), (154, 2), (155, 1), (156, 2), (157, 1), (158, 1), (159, 2), (160, 2), (161, 1), (162, 3), (163, 1), (164, 6), (165, 1), (166, 1), (167, 2), (168, 5), (169, 1), (170, 4), (171, 1), (172, 1), (173, 1), (174, 1), (175, 1), (176, 3), (177, 1), (178, 1), (179, 1), (180, 2), (181, 1), (182, 1), (183, 1), (184, 1), (185, 1), (186, 1), (187, 1), (188, 1), (189, 2), (190, 1), (191, 3), (192, 1), (193, 2), (194, 1), (195, 1), (196, 1), (197, 2), (198, 2), (199, 1), (200, 3), (201, 1), (202, 1), (203, 1), (204, 1), (205, 1), (206, 2), (207, 1), (208, 1), (209, 1), (210, 1), (211, 1), (212, 1), (213, 1), (214, 1), (215, 1), (216, 1), (217, 2), (218, 1), (219, 1), (220, 2), (221, 1), (222, 1), (223, 1), (224, 1), (225, 2), (226, 1), (227, 2), (228, 1), (229, 2), (230, 1), (231, 1), (232, 4), (233, 1), (234, 3), (235, 2), (236, 1), (237, 1), (238, 1), (239, 2), (240, 15), (241, 1), (242, 1), (243, 2), (244, 1), (245, 2), (246, 1), (247, 1), (248, 1), (249, 1), (250, 1), (251, 15), (252, 1), (253, 2), (254, 1), (255, 1), (256, 2), (257, 1), (258, 1), (259, 2), (260, 1), (261, 4), (262, 1), (263, 2), (264, 2), (265, 1), (266, 1), (267, 1), (268, 1), (269, 1), (270, 2), (271, 3), (272, 1), (273, 1), (274, 1), (275, 3), (276, 1), (277, 1), (278, 1), (279, 1), (280, 1), (281, 1), (282, 4), (283, 2), (284, 1), (285, 1), (286, 1), (287, 1), (288, 2), (289, 1), (290, 1), (291, 1), (292, 1), (293, 1), (294, 1), (295, 1), (296, 1), (297, 1), (298, 1), (299, 1), (300, 1), (301, 1), (302, 1), (303, 1), (304, 1), (305, 1), (306, 1), (307, 1), (308, 2), (309, 2), (310, 1), (311, 2), (312, 1), (313, 1), (314, 1), (315, 1), (316, 1), (317, 3), (318, 1), (319, 1), (320, 1), (321, 10), (322, 1), (323, 1), (324, 1), (325, 1), (326, 1), (327, 1), (328, 1), (329, 1), (330, 2), (331, 1), (332, 1), (333, 1), (334, 1), (335, 1), (336, 1), (337, 1), (338, 2), (339, 1), (340, 3), (341, 1), (342, 1), (343, 1), (344, 1), (345, 1), (346, 1), (347, 1), (348, 1), (349, 1), (350, 1), (351, 1), (352, 1), (353, 1), (354, 2), (355, 2), (356, 1), (357, 1), (358, 1), (359, 1), (360, 1), (361, 1), (362, 1), (363, 1), (364, 1), (365, 13), (366, 5), (367, 2), (368, 1), (369, 2), (370, 1), (371, 1), (372, 1), (373, 1), (374, 1), (375, 1), (376, 2), (377, 1), (378, 1), (379, 2), (380, 1), (381, 3), (382, 1), (383, 2), (384, 1), (385, 1), (386, 16), (387, 1), (388, 1), (389, 4), (390, 1), (391, 2), (392, 1), (393, 1), (394, 1), (395, 1), (396, 5), (397, 4), (398, 1), (399, 1), (400, 2), (401, 1), (402, 1), (403, 1), (404, 1), (405, 1), (406, 1), (407, 1), (408, 1), (409, 5), (410, 2), (411, 1), (412, 1), (413, 1), (414, 1), (415, 1), (416, 1), (417, 1), (418, 3), (419, 4), (420, 1)], [(2, 1), (13, 1), (15, 1), (22, 1), (34, 2), (48, 1), (49, 1), (50, 1), (51, 2), (68, 1), (80, 1), (83, 1), (88, 1), (102, 1), (107, 2), (109, 1), (111, 3), (116, 1), (118, 1), (133, 1), (142, 1), (157, 1), (162, 3), (167, 1), (170, 4), (175, 1), (182, 1), (187, 4), (188, 1), (189, 2), (215, 1), (217, 2), (220, 3), (227, 2), (232, 3), (238, 1), (248, 1), (250, 1), (251, 3), (261, 5), (262, 2), (270, 1), (271, 1), (279, 4), (282, 2), (287, 2), (292, 2), (310, 1), (313, 1), (314, 1), (319, 1), (321, 4), (329, 1), (337, 2), (346, 2), (350, 1), (354, 3), (356, 1), (360, 1), (367, 1), (374, 1), (376, 6), (378, 1), (379, 1), (386, 1), (389, 1), (390, 1), (394, 1), (406, 2), (409, 1), (411, 2), (415, 1), (419, 1), (421, 1), (422, 1), (423, 1), (424, 1), (425, 1), (426, 1), (427, 2), (428, 1), (429, 2), (430, 1), (431, 1), (432, 1), (433, 1), (434, 1), (435, 1), (436, 1), (437, 1), (438, 1), (439, 1), (440, 1), (441, 1), (442, 1), (443, 1), (444, 1), (445, 1), (446, 1), (447, 1), (448, 2), (449, 1), (450, 1), (451, 1), (452, 1), (453, 1), (454, 1), (455, 1), (456, 1), (457, 3), (458, 1), (459, 1), (460, 1), (461, 1), (462, 8), (463, 1), (464, 1), (465, 4), (466, 1), (467, 2), (468, 1), (469, 1), (470, 1), (471, 1), (472, 1), (473, 1), (474, 1), (475, 1), (476, 1), (477, 1), (478, 1), (479, 1), (480, 1), (481, 1), (482, 1), (483, 1), (484, 1), (485, 1), (486, 1), (487, 1), (488, 1), (489, 1), (490, 1), (491, 2), (492, 1), (493, 1), (494, 1), (495, 1), (496, 1), (497, 1), (498, 1), (499, 1), (500, 1), (501, 1), (502, 2), (503, 3), (504, 1), (505, 1), (506, 1), (507, 1), (508, 2), (509, 1), (510, 5), (511, 1), (512, 1), (513, 2), (514, 1), (515, 1), (516, 1), (517, 1), (518, 1), (519, 1), (520, 1), (521, 1), (522, 2), (523, 1), (524, 1), (525, 1), (526, 1), (527, 1), (528, 2), (529, 1), (530, 1), (531, 1), (532, 1), (533, 1), (534, 1), (535, 2), (536, 1), (537, 1), (538, 1), (539, 1), (540, 1), (541, 1), (542, 1), (543, 1), (544, 1), (545, 2), (546, 1), (547, 1), (548, 1), (549, 1), (550, 3), (551, 1), (552, 1), (553, 2), (554, 1), (555, 1), (556, 2), (557, 1), (558, 2), (559, 1), (560, 1), (561, 1), (562, 3), (563, 1), (564, 1), (565, 1), (566, 1), (567, 1), (568, 1), (569, 1), (570, 2), (571, 1), (572, 1), (573, 1), (574, 1), (575, 1), (576, 1), (577, 1), (578, 2), (579, 1), (580, 1), (581, 1), (582, 1), (583, 2), (584, 1), (585, 1), (586, 1), (587, 1), (588, 1), (589, 1), (590, 1), (591, 3), (592, 4), (593, 1), (594, 3), (595, 1), (596, 1), (597, 1), (598, 1), (599, 1), (600, 1), (601, 1), (602, 1), (603, 1), (604, 1), (605, 1), (606, 1), (607, 1), (608, 1), (609, 1), (610, 8), (611, 2), (612, 1), (613, 1), (614, 1), (615, 8), (616, 2), (617, 1), (618, 2), (619, 1), (620, 2), (621, 1), (622, 1), (623, 1), (624, 1), (625, 1), (626, 1), (627, 1), (628, 1), (629, 1), (630, 1), (631, 1), (632, 1), (633, 3), (634, 1), (635, 1), (636, 1), (637, 1), (638, 2), (639, 1), (640, 1), (641, 1), (642, 1), (643, 1), (644, 1), (645, 2), (646, 1), (647, 1), (648, 1), (649, 1), (650, 1), (651, 3), (652, 1), (653, 1), (654, 1), (655, 1), (656, 2), (657, 1), (658, 1), (659, 2), (660, 1), (661, 5), (662, 1), (663, 1), (664, 1), (665, 1), (666, 1), (667, 2), (668, 1), (669, 1), (670, 3), (671, 3), (672, 2), (673, 1), (674, 1), (675, 1), (676, 2), (677, 1), (678, 1), (679, 1), (680, 10), (681, 1), (682, 2), (683, 1), (684, 1), (685, 1), (686, 1), (687, 1), (688, 1), (689, 1), (690, 1), (691, 1), (692, 1), (693, 1), (694, 1), (695, 1), (696, 1), (697, 1), (698, 1), (699, 1), (700, 1), (701, 3), (702, 1), (703, 1), (704, 1), (705, 1), (706, 1), (707, 3), (708, 1), (709, 1), (710, 1), (711, 1), (712, 1), (713, 1), (714, 1), (715, 1), (716, 1), (717, 1), (718, 1), (719, 1), (720, 2), (721, 1), (722, 1), (723, 1), (724, 1), (725, 2), (726, 1), (727, 1), (728, 1), (729, 1), (730, 4), (731, 1), (732, 1), (733, 1), (734, 1), (735, 1), (736, 4), (737, 1), (738, 2), (739, 1), (740, 1), (741, 1), (742, 1), (743, 2), (744, 2), (745, 1), (746, 2), (747, 1), (748, 1), (749, 1), (750, 1), (751, 2), (752, 2), (753, 1), (754, 1), (755, 1), (756, 1), (757, 3), (758, 1), (759, 1), (760, 1), (761, 4), (762, 3), (763, 1), (764, 1)], [(7, 1), (12, 1), (15, 4), (17, 1), (18, 16), (22, 1), (24, 1), (25, 2), (29, 5), (30, 1), (31, 2), (32, 1), (36, 1), (44, 1), (54, 1), (56, 2), (61, 1), (69, 1), (76, 1), (79, 1), (81, 1), (82, 1), (83, 1), (85, 1), (86, 1), (87, 1), (91, 1), (93, 2), (97, 1), (107, 1), (115, 1), (118, 1), (133, 1), (137, 1), (138, 2), (140, 1), (145, 1), (150, 2), (157, 1), (162, 3), (164, 6), (177, 1), (179, 2), (181, 1), (186, 2), (187, 2), (191, 1), (200, 3), (202, 2), (205, 1), (217, 3), (220, 1), (224, 1), (226, 1), (227, 4), (229, 2), (234, 1), (241, 1), (246, 1), (250, 1), (251, 38), (256, 2), (259, 1), (261, 3), (262, 3), (270, 4), (282, 1), (288, 3), (305, 2), (314, 2), (321, 12), (331, 2), (334, 2), (338, 1), (343, 1), (354, 1), (355, 1), (356, 1), (364, 1), (376, 1), (379, 2), (386, 18), (388, 1), (391, 1), (394, 1), (402, 7), (406, 2), (410, 1), (411, 1), (414, 1), (415, 3), (419, 2), (427, 2), (433, 1), (444, 1), (461, 16), (462, 1), (487, 1), (495, 1), (503, 5), (537, 1), (544, 1), (553, 2), (559, 2), (567, 1), (573, 1), (590, 1), (593, 1), (594, 3), (598, 1), (601, 1), (624, 1), (629, 1), (645, 4), (650, 1), (654, 1), (660, 2), (661, 4), (672, 5), (673, 1), (674, 1), (680, 6), (682, 1), (684, 2), (693, 1), (708, 1), (720, 2), (722, 1), (725, 1), (727, 3), (728, 1), (736, 1), (744, 1), (751, 2), (758, 4), (765, 1), (766, 1), (767, 1), (768, 1), (769, 1), (770, 1), (771, 2), (772, 1), (773, 1), (774, 2), (775, 1), (776, 1), (777, 1), (778, 2), (779, 2), (780, 1), (781, 1), (782, 1), (783, 2), (784, 1), (785, 1), (786, 1), (787, 1), (788, 1), (789, 1), (790, 1), (791, 1), (792, 1), (793, 2), (794, 1), (795, 1), (796, 1), (797, 1), (798, 2), (799, 1), (800, 1), (801, 4), (802, 1), (803, 4), (804, 1), (805, 1), (806, 1), (807, 4), (808, 1), (809, 3), (810, 1), (811, 1), (812, 1), (813, 1), (814, 1), (815, 1), (816, 2), (817, 1), (818, 1), (819, 1), (820, 1), (821, 1), (822, 1), (823, 1), (824, 1), (825, 1), (826, 1), (827, 1), (828, 4), (829, 1), (830, 1), (831, 1), (832, 1), (833, 1), (834, 2), (835, 1), (836, 2), (837, 1), (838, 1), (839, 3), (840, 1), (841, 1), (842, 1), (843, 2), (844, 1), (845, 2), (846, 1), (847, 1), (848, 1), (849, 3), (850, 1), (851, 1), (852, 1), (853, 1), (854, 1), (855, 1), (856, 1), (857, 1), (858, 2), (859, 5), (860, 1), (861, 1), (862, 1), (863, 1), (864, 4), (865, 2), (866, 2), (867, 1), (868, 1), (869, 2), (870, 1), (871, 1), (872, 3), (873, 3), (874, 3), (875, 1), (876, 1), (877, 3), (878, 1), (879, 1), (880, 1), (881, 13), (882, 1), (883, 1), (884, 2), (885, 1), (886, 2), (887, 2), (888, 1), (889, 2), (890, 1), (891, 3), (892, 1), (893, 1), (894, 1), (895, 2), (896, 1), (897, 1), (898, 1), (899, 1), (900, 1), (901, 1), (902, 1), (903, 2), (904, 1), (905, 1), (906, 2), (907, 1), (908, 1), (909, 1), (910, 1), (911, 2), (912, 2), (913, 2), (914, 1), (915, 1), (916, 1), (917, 1), (918, 2), (919, 1), (920, 1), (921, 2), (922, 1), (923, 1), (924, 1), (925, 1), (926, 1), (927, 1), (928, 1), (929, 2), (930, 1), (931, 1), (932, 1), (933, 1), (934, 1), (935, 5), (936, 1), (937, 1), (938, 18), (939, 1), (940, 1), (941, 1), (942, 1), (943, 2), (944, 1), (945, 1), (946, 1), (947, 1), (948, 1), (949, 1), (950, 1), (951, 1), (952, 1), (953, 3), (954, 1), (955, 1), (956, 1), (957, 1), (958, 1), (959, 1), (960, 1), (961, 1), (962, 1), (963, 1), (964, 1), (965, 3), (966, 1), (967, 1), (968, 1), (969, 1), (970, 1), (971, 2), (972, 8), (973, 1), (974, 1), (975, 1), (976, 3), (977, 1), (978, 1), (979, 1), (980, 1), (981, 1), (982, 1), (983, 1), (984, 1), (985, 1), (986, 1), (987, 1), (988, 1), (989, 1), (990, 1), (991, 1), (992, 1), (993, 1), (994, 2), (995, 1), (996, 3), (997, 1), (998, 1), (999, 1), (1000, 1), (1001, 2), (1002, 1), (1003, 1), (1004, 2), (1005, 1), (1006, 1), (1007, 1), (1008, 1), (1009, 1), (1010, 2), (1011, 2), (1012, 1), (1013, 1), (1014, 1), (1015, 2), (1016, 2), (1017, 1), (1018, 2), (1019, 1), (1020, 1), (1021, 1), (1022, 1), (1023, 1), (1024, 2), (1025, 1), (1026, 1), (1027, 1), (1028, 1), (1029, 3)], [(3, 1), (9, 1), (22, 1), (25, 1), (37, 1), (40, 1), (50, 2), (51, 1), (55, 1), (64, 2), (77, 2), (85, 4), (93, 2), (97, 4), (106, 1), (107, 2), (133, 4), (134, 1), (145, 2), (151, 1), (159, 1), (162, 3), (164, 2), (170, 1), (176, 3), (187, 1), (188, 1), (191, 2), (193, 1), (205, 1), (216, 1), (217, 1), (218, 1), (219, 1), (224, 1), (227, 12), (232, 3), (240, 1), (249, 2), (251, 42), (259, 1), (260, 1), (261, 11), (268, 1), (271, 1), (279, 1), (282, 3), (287, 1), (294, 1), (321, 24), (329, 2), (330, 2), (331, 1), (337, 6), (342, 1), (344, 3), (345, 1), (353, 2), (354, 1), (356, 3), (362, 2), (367, 2), (369, 2), (371, 4), (373, 2), (374, 2), (376, 8), (378, 2), (391, 1), (394, 1), (406, 6), (409, 3), (410, 1), (412, 1), (413, 1), (418, 1), (419, 5), (420, 5), (457, 1), (461, 1), (470, 2), (489, 1), (507, 1), (511, 2), (518, 3), (522, 1), (536, 1), (543, 1), (544, 5), (545, 1), (559, 1), (560, 1), (565, 1), (574, 3), (585, 1), (590, 2), (591, 2), (604, 1), (614, 1), (616, 2), (621, 1), (626, 1), (650, 3), (657, 1), (672, 5), (690, 1), (692, 1), (695, 3), (708, 1), (713, 1), (715, 1), (718, 1), (720, 1), (725, 3), (726, 1), (727, 1), (736, 2), (738, 9), (739, 1), (741, 1), (744, 4), (745, 1), (750, 3), (753, 1), (758, 6), (760, 1), (761, 2), (763, 1), (768, 1), (770, 2), (771, 1), (775, 1), (793, 2), (794, 1), (826, 1), (836, 1), (837, 1), (838, 2), (845, 1), (847, 1), (869, 1), (873, 2), (886, 1), (899, 2), (908, 1), (921, 1), (922, 3), (932, 1), (934, 1), (942, 1), (943, 2), (945, 2), (958, 2), (959, 3), (962, 1), (983, 1), (995, 1), (1020, 1), (1027, 1), (1030, 1), (1031, 1), (1032, 1), (1033, 1), (1034, 2), (1035, 1), (1036, 1), (1037, 1), (1038, 1), (1039, 1), (1040, 1), (1041, 1), (1042, 1), (1043, 1), (1044, 1), (1045, 1), (1046, 1), (1047, 1), (1048, 1), (1049, 1), (1050, 2), (1051, 1), (1052, 2), (1053, 1), (1054, 1), (1055, 1), (1056, 1), (1057, 1), (1058, 1), (1059, 1), (1060, 1), (1061, 1), (1062, 1), (1063, 1), (1064, 1), (1065, 1), (1066, 2), (1067, 1), (1068, 4), (1069, 1), (1070, 1), (1071, 1), (1072, 1), (1073, 1), (1074, 1), (1075, 1), (1076, 1), (1077, 1), (1078, 1), (1079, 3), (1080, 1), (1081, 1), (1082, 1), (1083, 1), (1084, 1), (1085, 1), (1086, 2), (1087, 1), (1088, 1), (1089, 1), (1090, 1), (1091, 3), (1092, 1), (1093, 20), (1094, 1), (1095, 1), (1096, 4), (1097, 3), (1098, 1), (1099, 1), (1100, 9), (1101, 1), (1102, 1), (1103, 1), (1104, 1), (1105, 1), (1106, 1), (1107, 1), (1108, 1), (1109, 1), (1110, 1), (1111, 1), (1112, 1), (1113, 1), (1114, 3), (1115, 1), (1116, 1), (1117, 1), (1118, 2), (1119, 2), (1120, 1), (1121, 1), (1122, 1), (1123, 1), (1124, 1), (1125, 1), (1126, 1), (1127, 1), (1128, 1), (1129, 1), (1130, 1), (1131, 1), (1132, 1), (1133, 1), (1134, 1), (1135, 1), (1136, 1), (1137, 1), (1138, 1), (1139, 1), (1140, 1), (1141, 1), (1142, 1), (1143, 2), (1144, 1), (1145, 1), (1146, 1), (1147, 1), (1148, 1), (1149, 1), (1150, 1), (1151, 2), (1152, 1), (1153, 1), (1154, 2), (1155, 1), (1156, 3), (1157, 1), (1158, 1), (1159, 1), (1160, 1), (1161, 9), (1162, 2), (1163, 1), (1164, 1), (1165, 1), (1166, 1), (1167, 1), (1168, 1), (1169, 1), (1170, 1), (1171, 1), (1172, 1), (1173, 1), (1174, 1), (1175, 1), (1176, 1), (1177, 1), (1178, 1), (1179, 1), (1180, 1), (1181, 1), (1182, 1), (1183, 1), (1184, 1), (1185, 1), (1186, 3), (1187, 1), (1188, 7), (1189, 1), (1190, 1), (1191, 2), (1192, 1), (1193, 2), (1194, 1), (1195, 1), (1196, 2), (1197, 1), (1198, 1), (1199, 1), (1200, 1), (1201, 1), (1202, 1), (1203, 1), (1204, 2), (1205, 1), (1206, 2), (1207, 1), (1208, 1), (1209, 1), (1210, 1), (1211, 1), (1212, 1), (1213, 1), (1214, 3), (1215, 1), (1216, 2), (1217, 1), (1218, 1), (1219, 1), (1220, 1), (1221, 1), (1222, 2), (1223, 1), (1224, 1), (1225, 20), (1226, 2), (1227, 2), (1228, 1), (1229, 1), (1230, 1), (1231, 2), (1232, 1), (1233, 1), (1234, 1), (1235, 1), (1236, 2), (1237, 2), (1238, 2), (1239, 4), (1240, 1), (1241, 1), (1242, 1), (1243, 1), (1244, 1), (1245, 2), (1246, 1), (1247, 1), (1248, 1), (1249, 1), (1250, 1), (1251, 1), (1252, 1), (1253, 1), (1254, 1), (1255, 1), (1256, 1), (1257, 4), (1258, 1), (1259, 1), (1260, 1), (1261, 1), (1262, 1), (1263, 7), (1264, 1), (1265, 1), (1266, 1), (1267, 1), (1268, 2), (1269, 1), (1270, 1), (1271, 1), (1272, 1), (1273, 1), (1274, 1), (1275, 1), (1276, 1), (1277, 1), (1278, 1), (1279, 1), (1280, 1), (1281, 1), (1282, 1), (1283, 1), (1284, 2), (1285, 1), (1286, 1), (1287, 1), (1288, 3), (1289, 1), (1290, 1), (1291, 5), (1292, 1), (1293, 1), (1294, 1), (1295, 1), (1296, 1), (1297, 1), (1298, 3), (1299, 3), (1300, 1), (1301, 7), (1302, 1), (1303, 1), (1304, 1), (1305, 4), (1306, 1), (1307, 1), (1308, 1), (1309, 1), (1310, 1), (1311, 1), (1312, 1), (1313, 1), (1314, 1), (1315, 1), (1316, 1), (1317, 1), (1318, 1), (1319, 1), (1320, 1), (1321, 1), (1322, 1), (1323, 2), (1324, 1), (1325, 1), (1326, 1), (1327, 4), (1328, 1), (1329, 1), (1330, 1), (1331, 2), (1332, 1), (1333, 1), (1334, 1), (1335, 1), (1336, 1), (1337, 1), (1338, 2), (1339, 1), (1340, 1), (1341, 1), (1342, 1), (1343, 1), (1344, 1), (1345, 1), (1346, 1), (1347, 1), (1348, 1), (1349, 2), (1350, 1), (1351, 1), (1352, 1), (1353, 1), (1354, 3), (1355, 1), (1356, 4)], [(0, 1), (3, 1), (5, 2), (12, 3), (18, 1), (25, 2), (30, 2), (49, 1), (54, 1), (61, 1), (88, 2), (93, 1), (96, 1), (98, 7), (118, 1), (133, 3), (140, 2), (149, 2), (162, 1), (168, 6), (174, 2), (175, 1), (191, 2), (197, 7), (200, 1), (215, 2), (217, 6), (224, 1), (227, 2), (234, 1), (236, 16), (249, 3), (250, 4), (251, 1), (256, 1), (261, 1), (271, 1), (282, 1), (283, 15), (288, 2), (289, 1), (303, 1), (305, 1), (313, 1), (321, 3), (329, 1), (330, 1), (354, 2), (356, 2), (376, 1), (379, 1), (382, 3), (391, 2), (402, 1), (409, 1), (411, 3), (414, 1), (418, 6), (420, 7), (424, 3), (433, 1), (436, 2), (442, 1), (482, 1), (502, 1), (507, 7), (522, 1), (534, 1), (536, 1), (544, 1), (550, 1), (557, 1), (559, 1), (574, 1), (579, 1), (584, 1), (593, 1), (594, 3), (598, 1), (621, 3), (632, 2), (651, 1), (654, 1), (655, 1), (660, 1), (667, 1), (672, 3), (682, 2), (709, 1), (711, 1), (720, 1), (738, 2), (739, 2), (759, 1), (765, 1), (775, 1), (778, 1), (794, 3), (795, 1), (803, 1), (838, 1), (849, 1), (852, 2), (863, 1), (869, 1), (883, 2), (887, 1), (889, 1), (894, 1), (897, 1), (899, 2), (900, 1), (924, 1), (934, 1), (935, 2), (946, 1), (959, 1), (960, 1), (969, 1), (972, 1), (976, 3), (983, 3), (1031, 1), (1034, 2), (1037, 1), (1040, 1), (1046, 2), (1050, 2), (1115, 1), (1130, 1), (1145, 1), (1158, 3), (1204, 2), (1215, 1), (1224, 1), (1237, 1), (1256, 1), (1259, 2), (1262, 1), (1265, 1), (1273, 1), (1278, 4), (1294, 1), (1311, 1), (1357, 1), (1358, 1), (1359, 1), (1360, 1), (1361, 1), (1362, 1), (1363, 1), (1364, 1), (1365, 1), (1366, 1), (1367, 3), (1368, 1), (1369, 1), (1370, 1), (1371, 1), (1372, 1), (1373, 1), (1374, 1), (1375, 1), (1376, 1), (1377, 1), (1378, 3), (1379, 1), (1380, 1), (1381, 5), (1382, 1), (1383, 1), (1384, 1), (1385, 1), (1386, 6), (1387, 13), (1388, 1), (1389, 1), (1390, 1), (1391, 3), (1392, 1), (1393, 1), (1394, 1), (1395, 1), (1396, 1), (1397, 1), (1398, 2), (1399, 2), (1400, 1), (1401, 1), (1402, 1), (1403, 1), (1404, 2), (1405, 1), (1406, 1), (1407, 1), (1408, 1), (1409, 3), (1410, 2), (1411, 2), (1412, 2), (1413, 1), (1414, 1), (1415, 2), (1416, 4), (1417, 1), (1418, 1), (1419, 1), (1420, 1), (1421, 2), (1422, 1), (1423, 1), (1424, 2), (1425, 1), (1426, 1), (1427, 1), (1428, 7), (1429, 1), (1430, 1), (1431, 1), (1432, 3), (1433, 2), (1434, 1), (1435, 1), (1436, 1), (1437, 1), (1438, 1), (1439, 1), (1440, 1), (1441, 1), (1442, 1), (1443, 3), (1444, 1), (1445, 1), (1446, 1), (1447, 4), (1448, 1), (1449, 1), (1450, 3), (1451, 1), (1452, 1), (1453, 1), (1454, 1), (1455, 1), (1456, 1), (1457, 1), (1458, 1), (1459, 1), (1460, 1), (1461, 2), (1462, 1), (1463, 4), (1464, 1), (1465, 3), (1466, 1), (1467, 1), (1468, 1), (1469, 1), (1470, 1), (1471, 1), (1472, 1), (1473, 3), (1474, 1), (1475, 2), (1476, 1), (1477, 1), (1478, 1), (1479, 1), (1480, 2), (1481, 1), (1482, 1), (1483, 1), (1484, 1), (1485, 1), (1486, 1), (1487, 1), (1488, 2), (1489, 1), (1490, 1), (1491, 2), (1492, 1), (1493, 1), (1494, 1), (1495, 1), (1496, 1), (1497, 1), (1498, 1), (1499, 1), (1500, 1), (1501, 1), (1502, 1), (1503, 2), (1504, 1), (1505, 2), (1506, 1), (1507, 1), (1508, 6), (1509, 1), (1510, 1), (1511, 2), (1512, 3), (1513, 1), (1514, 1), (1515, 1), (1516, 1), (1517, 2), (1518, 3), (1519, 1), (1520, 1), (1521, 1), (1522, 1), (1523, 1), (1524, 2), (1525, 1), (1526, 1), (1527, 3), (1528, 1), (1529, 1), (1530, 3), (1531, 1), (1532, 1), (1533, 1), (1534, 1), (1535, 1), (1536, 1), (1537, 7), (1538, 1), (1539, 1), (1540, 3), (1541, 1), (1542, 1), (1543, 1), (1544, 1), (1545, 1), (1546, 3), (1547, 1), (1548, 1), (1549, 1), (1550, 1), (1551, 3), (1552, 2), (1553, 1), (1554, 1), (1555, 1), (1556, 1), (1557, 1), (1558, 1), (1559, 2), (1560, 1), (1561, 1), (1562, 1), (1563, 1), (1564, 1), (1565, 6), (1566, 1)], [(15, 2), (16, 1), (18, 1), (22, 1), (25, 2), (34, 6), (37, 1), (39, 1), (45, 7), (48, 1), (51, 3), (62, 1), (68, 2), (76, 1), (77, 1), (79, 1), (83, 1), (85, 2), (87, 2), (91, 1), (93, 1), (97, 8), (98, 3), (99, 1), (102, 1), (107, 5), (109, 1), (124, 1), (132, 1), (137, 2), (142, 1), (144, 2), (150, 1), (151, 1), (159, 1), (162, 2), (164, 1), (175, 1), (176, 2), (180, 1), (188, 3), (189, 16), (204, 1), (210, 1), (213, 2), (215, 1), (217, 3), (220, 3), (224, 1), (227, 1), (228, 1), (229, 3), (232, 1), (234, 2), (241, 2), (250, 1), (251, 20), (256, 1), (259, 1), (261, 2), (262, 1), (270, 16), (271, 4), (273, 2), (278, 7), (280, 1), (282, 1), (283, 1), (287, 2), (288, 1), (292, 1), (309, 1), (311, 1), (314, 2), (321, 11), (329, 1), (332, 1), (337, 1), (354, 3), (362, 2), (363, 2), (367, 1), (369, 2), (371, 1), (376, 1), (378, 3), (386, 1), (391, 3), (406, 1), (407, 2), (409, 2), (411, 4), (419, 4), (420, 3), (427, 1), (428, 2), (433, 2), (437, 11), (445, 1), (462, 2), (469, 6), (471, 2), (476, 1), (489, 1), (491, 1), (494, 3), (495, 1), (502, 1), (504, 7), (517, 8), (518, 1), (528, 1), (536, 1), (549, 1), (550, 2), (576, 1), (580, 1), (581, 4), (591, 3), (592, 6), (612, 2), (624, 4), (628, 1), (629, 1), (632, 1), (643, 1), (645, 1), (650, 1), (654, 2), (659, 1), (660, 1), (666, 1), (672, 3), (675, 10), (681, 1), (695, 1), (700, 1), (708, 6), (711, 1), (725, 1), (727, 3), (736, 3), (738, 4), (744, 1), (748, 1), (749, 1), (758, 1), (761, 1), (765, 1), (775, 1), (780, 1), (797, 4), (803, 4), (817, 2), (828, 3), (836, 1), (837, 1), (838, 1), (844, 1), (860, 1), (863, 1), (872, 1), (877, 1), (886, 1), (887, 1), (892, 2), (894, 2), (905, 1), (919, 1), (921, 3), (932, 1), (935, 1), (950, 2), (952, 2), (963, 1), (965, 1), (974, 1), (976, 1), (978, 1), (979, 1), (982, 1), (983, 1), (987, 1), (988, 2), (991, 2), (1023, 2), (1034, 1), (1049, 3), (1050, 2), (1080, 1), (1090, 2), (1092, 5), (1142, 1), (1152, 1), (1157, 1), (1167, 1), (1206, 1), (1215, 1), (1216, 6), (1232, 1), (1235, 2), (1262, 1), (1263, 1), (1270, 1), (1273, 1), (1299, 1), (1311, 2), (1314, 8), (1355, 1), (1360, 1), (1372, 1), (1373, 1), (1383, 2), (1397, 1), (1419, 1), (1428, 1), (1438, 3), (1440, 4), (1451, 1), (1510, 2), (1511, 1), (1527, 1), (1561, 1), (1567, 1), (1568, 1), (1569, 1), (1570, 2), (1571, 2), (1572, 1), (1573, 1), (1574, 1), (1575, 1), (1576, 2), (1577, 1), (1578, 1), (1579, 1), (1580, 2), (1581, 14), (1582, 1), (1583, 1), (1584, 1), (1585, 1), (1586, 1), (1587, 1), (1588, 1), (1589, 1), (1590, 1), (1591, 1), (1592, 1), (1593, 1), (1594, 1), (1595, 2), (1596, 1), (1597, 1), (1598, 1), (1599, 1), (1600, 1), (1601, 1), (1602, 2), (1603, 6), (1604, 1), (1605, 1), (1606, 1), (1607, 1), (1608, 1), (1609, 1), (1610, 1), (1611, 3), (1612, 1), (1613, 1), (1614, 1), (1615, 1), (1616, 1), (1617, 1), (1618, 2), (1619, 1), (1620, 1), (1621, 1), (1622, 1), (1623, 4), (1624, 1), (1625, 1), (1626, 1), (1627, 1), (1628, 1), (1629, 1), (1630, 1), (1631, 1), (1632, 1), (1633, 1), (1634, 1), (1635, 1), (1636, 1), (1637, 2), (1638, 1), (1639, 1), (1640, 1), (1641, 1), (1642, 1), (1643, 1), (1644, 1), (1645, 1), (1646, 1), (1647, 1), (1648, 1), (1649, 1), (1650, 2), (1651, 1), (1652, 3), (1653, 1), (1654, 1), (1655, 8), (1656, 1), (1657, 1), (1658, 4), (1659, 2), (1660, 1), (1661, 5), (1662, 1), (1663, 2), (1664, 1), (1665, 1), (1666, 1), (1667, 1), (1668, 1), (1669, 4), (1670, 1), (1671, 1), (1672, 1), (1673, 1), (1674, 1), (1675, 1), (1676, 1), (1677, 1), (1678, 1), (1679, 1), (1680, 1), (1681, 1), (1682, 1), (1683, 1), (1684, 1), (1685, 1), (1686, 1), (1687, 1), (1688, 1), (1689, 1), (1690, 1), (1691, 1), (1692, 1), (1693, 2), (1694, 1), (1695, 1), (1696, 2), (1697, 1), (1698, 1), (1699, 1), (1700, 1), (1701, 1), (1702, 1), (1703, 1), (1704, 1), (1705, 1), (1706, 1), (1707, 1), (1708, 1), (1709, 1), (1710, 2), (1711, 2), (1712, 1), (1713, 1), (1714, 2), (1715, 1), (1716, 1), (1717, 1), (1718, 1), (1719, 2), (1720, 1), (1721, 1), (1722, 1), (1723, 1), (1724, 1), (1725, 1), (1726, 1), (1727, 1)], [(4, 1), (12, 1), (17, 3), (24, 2), (25, 2), (30, 2), (35, 4), (36, 1), (37, 1), (39, 1), (45, 5), (50, 1), (56, 1), (61, 1), (64, 2), (68, 2), (69, 6), (70, 7), (74, 2), (76, 1), (79, 1), (81, 3), (82, 3), (83, 1), (85, 1), (86, 1), (91, 1), (93, 1), (97, 8), (107, 1), (108, 2), (112, 1), (115, 2), (133, 3), (137, 1), (140, 2), (148, 1), (150, 2), (151, 1), (157, 2), (162, 2), (164, 1), (165, 1), (175, 2), (177, 1), (182, 1), (188, 1), (191, 1), (202, 1), (205, 1), (213, 1), (217, 6), (222, 1), (224, 1), (227, 4), (229, 1), (234, 1), (238, 1), (240, 1), (248, 1), (250, 2), (251, 77), (259, 4), (261, 1), (262, 4), (263, 1), (271, 2), (279, 3), (283, 1), (284, 1), (288, 2), (290, 1), (291, 4), (296, 1), (300, 1), (303, 1), (305, 1), (321, 9), (330, 2), (332, 1), (337, 2), (354, 5), (356, 2), (359, 1), (360, 1), (367, 1), (371, 1), (372, 2), (376, 2), (378, 1), (386, 23), (388, 1), (389, 1), (401, 2), (402, 1), (407, 1), (408, 1), (409, 2), (410, 3), (411, 5), (415, 1), (419, 8), (420, 1), (428, 1), (429, 1), (433, 1), (441, 1), (449, 2), (458, 1), (462, 2), (464, 1), (468, 1), (477, 1), (478, 1), (486, 1), (488, 2), (495, 2), (499, 1), (506, 1), (511, 1), (524, 1), (560, 1), (584, 1), (585, 1), (591, 2), (593, 1), (594, 2), (598, 1), (616, 1), (621, 1), (629, 1), (645, 2), (661, 9), (672, 2), (680, 7), (713, 2), (720, 1), (722, 1), (726, 1), (727, 1), (730, 2), (734, 2), (738, 1), (749, 1), (770, 2), (773, 1), (774, 2), (778, 4), (780, 1), (791, 2), (792, 2), (793, 1), (809, 1), (816, 1), (833, 2), (838, 2), (841, 1), (843, 1), (844, 5), (845, 1), (849, 1), (851, 1), (853, 2), (859, 3), (863, 1), (872, 1), (880, 1), (889, 1), (894, 1), (898, 2), (902, 1), (909, 1), (911, 3), (912, 3), (913, 2), (922, 4), (924, 1), (925, 1), (934, 2), (935, 3), (940, 2), (946, 1), (948, 3), (950, 1), (952, 1), (963, 2), (965, 2), (966, 1), (971, 6), (977, 4), (983, 2), (989, 1), (1000, 1), (1001, 4), (1013, 1), (1016, 2), (1023, 3), (1025, 4), (1031, 2), (1062, 1), (1064, 1), (1075, 1), (1076, 1), (1090, 2), (1106, 1), (1110, 1), (1113, 1), (1118, 2), (1133, 1), (1150, 2), (1158, 2), (1171, 1), (1184, 1), (1199, 1), (1204, 1), (1206, 3), (1213, 1), (1216, 1), (1219, 1), (1222, 1), (1223, 5), (1224, 1), (1230, 1), (1255, 3), (1266, 1), (1273, 1), (1285, 1), (1291, 1), (1299, 2), (1301, 1), (1306, 1), (1309, 3), (1314, 1), (1317, 1), (1321, 1), (1329, 2), (1346, 1), (1360, 1), (1366, 1), (1375, 1), (1378, 1), (1396, 1), (1404, 1), (1430, 1), (1435, 1), (1444, 1), (1445, 1), (1455, 1), (1471, 1), (1480, 1), (1487, 1), (1493, 1), (1494, 1), (1511, 2), (1516, 1), (1521, 2), (1527, 1), (1546, 1), (1554, 1), (1559, 3), (1564, 1), (1571, 1), (1575, 1), (1597, 1), (1600, 31), (1603, 1), (1618, 1), (1629, 3), (1657, 1), (1659, 1), (1668, 3), (1670, 2), (1672, 1), (1676, 1), (1681, 1), (1694, 1), (1701, 2), (1709, 1), (1714, 2), (1728, 1), (1729, 1), (1730, 1), (1731, 1), (1732, 1), (1733, 1), (1734, 1), (1735, 1), (1736, 1), (1737, 2), (1738, 1), (1739, 1), (1740, 1), (1741, 1), (1742, 1), (1743, 1), (1744, 1), (1745, 1), (1746, 1), (1747, 1), (1748, 1), (1749, 1), (1750, 1), (1751, 1), (1752, 1), (1753, 2), (1754, 1), (1755, 1), (1756, 1), (1757, 1), (1758, 1), (1759, 1), (1760, 2), (1761, 2), (1762, 1), (1763, 1), (1764, 1), (1765, 1), (1766, 1), (1767, 1), (1768, 1), (1769, 1), (1770, 1), (1771, 1), (1772, 1), (1773, 1), (1774, 1), (1775, 1), (1776, 6), (1777, 1), (1778, 1), (1779, 1), (1780, 3), (1781, 1), (1782, 1), (1783, 1), (1784, 1), (1785, 1), (1786, 1), (1787, 1), (1788, 1), (1789, 1), (1790, 1), (1791, 1), (1792, 1), (1793, 1), (1794, 1), (1795, 1), (1796, 1), (1797, 1), (1798, 1), (1799, 1), (1800, 1), (1801, 1), (1802, 1), (1803, 1), (1804, 1), (1805, 23), (1806, 1), (1807, 1), (1808, 1), (1809, 4), (1810, 1), (1811, 1), (1812, 1), (1813, 1), (1814, 1), (1815, 2), (1816, 1), (1817, 1), (1818, 1), (1819, 1), (1820, 2), (1821, 1), (1822, 1), (1823, 1), (1824, 1), (1825, 1), (1826, 2), (1827, 1), (1828, 1), (1829, 1), (1830, 5), (1831, 1), (1832, 1), (1833, 1), (1834, 1), (1835, 3), (1836, 1), (1837, 1), (1838, 2), (1839, 1), (1840, 1), (1841, 1), (1842, 1), (1843, 1), (1844, 1), (1845, 2), (1846, 1), (1847, 2), (1848, 1), (1849, 1), (1850, 3), (1851, 1), (1852, 1), (1853, 1), (1854, 1), (1855, 1), (1856, 1), (1857, 1), (1858, 1), (1859, 2), (1860, 1), (1861, 1), (1862, 1), (1863, 5), (1864, 1), (1865, 1), (1866, 1), (1867, 1), (1868, 7), (1869, 2), (1870, 1), (1871, 1), (1872, 1), (1873, 4), (1874, 1), (1875, 1), (1876, 1), (1877, 1), (1878, 1), (1879, 1), (1880, 1), (1881, 2), (1882, 1), (1883, 1), (1884, 2), (1885, 3), (1886, 1), (1887, 1), (1888, 1), (1889, 1), (1890, 2), (1891, 1), (1892, 1), (1893, 1), (1894, 1), (1895, 1), (1896, 1), (1897, 1), (1898, 1), (1899, 2), (1900, 1), (1901, 1), (1902, 1), (1903, 1), (1904, 1), (1905, 1), (1906, 1), (1907, 1), (1908, 1), (1909, 3), (1910, 1), (1911, 1), (1912, 1), (1913, 1), (1914, 1), (1915, 1), (1916, 2), (1917, 2), (1918, 1), (1919, 2), (1920, 1), (1921, 1), (1922, 3), (1923, 1), (1924, 1), (1925, 1), (1926, 1), (1927, 1), (1928, 1), (1929, 1), (1930, 1), (1931, 1), (1932, 1), (1933, 4), (1934, 2), (1935, 1), (1936, 1), (1937, 1), (1938, 3), (1939, 1), (1940, 1), (1941, 1)], [(0, 3), (4, 2), (12, 3), (25, 1), (26, 1), (30, 1), (33, 1), (35, 1), (48, 1), (56, 1), (83, 3), (93, 1), (144, 1), (150, 1), (159, 1), (193, 1), (217, 2), (218, 1), (247, 1), (250, 1), (261, 1), (271, 1), (276, 1), (279, 1), (283, 3), (299, 1), (332, 1), (337, 2), (338, 2), (353, 2), (388, 1), (410, 1), (411, 5), (412, 1), (428, 1), (531, 1), (538, 1), (559, 1), (560, 1), (585, 1), (594, 1), (598, 2), (610, 3), (626, 1), (674, 3), (679, 1), (711, 2), (720, 1), (729, 1), (738, 1), (841, 1), (845, 1), (849, 1), (868, 1), (874, 1), (922, 1), (923, 2), (943, 3), (948, 1), (971, 1), (973, 1), (983, 1), (1027, 1), (1030, 1), (1038, 1), (1040, 1), (1043, 2), (1097, 1), (1156, 1), (1169, 1), (1213, 1), (1257, 1), (1263, 7), (1265, 1), (1266, 3), (1288, 5), (1312, 1), (1326, 1), (1358, 1), (1367, 1), (1380, 1), (1383, 1), (1398, 3), (1468, 3), (1489, 1), (1505, 1), (1506, 1), (1560, 1), (1586, 1), (1627, 1), (1629, 1), (1679, 1), (1721, 1), (1748, 1), (1832, 1), (1914, 1), (1940, 1), (1942, 1), (1943, 1), (1944, 1), (1945, 1), (1946, 1), (1947, 1), (1948, 1), (1949, 1), (1950, 1), (1951, 1), (1952, 1), (1953, 4), (1954, 7), (1955, 1), (1956, 1), (1957, 1), (1958, 3), (1959, 1), (1960, 1), (1961, 1), (1962, 1), (1963, 1), (1964, 1), (1965, 2), (1966, 1), (1967, 1), (1968, 1), (1969, 1), (1970, 1), (1971, 1), (1972, 1), (1973, 1), (1974, 1), (1975, 1), (1976, 3), (1977, 1), (1978, 1), (1979, 1), (1980, 1), (1981, 1), (1982, 1), (1983, 1), (1984, 1), (1985, 1), (1986, 1), (1987, 1), (1988, 1), (1989, 3), (1990, 1), (1991, 1), (1992, 2), (1993, 1), (1994, 1), (1995, 1), (1996, 1), (1997, 1), (1998, 1), (1999, 1)], [(10, 2), (12, 1), (14, 1), (15, 1), (17, 4), (25, 3), (29, 3), (36, 2), (55, 1), (56, 2), (62, 1), (64, 1), (68, 1), (69, 9), (70, 2), (74, 1), (76, 1), (79, 2), (82, 4), (83, 1), (86, 1), (87, 1), (97, 2), (99, 1), (109, 1), (111, 1), (112, 2), (115, 1), (118, 1), (133, 3), (144, 3), (145, 1), (151, 1), (162, 4), (166, 1), (177, 1), (186, 4), (202, 1), (227, 5), (228, 1), (232, 1), (233, 1), (241, 2), (250, 1), (251, 27), (259, 2), (261, 2), (262, 1), (263, 1), (271, 4), (274, 1), (275, 1), (276, 1), (278, 1), (282, 1), (290, 1), (291, 2), (297, 1), (305, 2), (311, 1), (321, 16), (329, 2), (330, 4), (332, 1), (337, 1), (343, 2), (346, 1), (352, 1), (354, 1), (356, 1), (359, 2), (360, 1), (361, 1), (362, 2), (371, 1), (373, 2), (378, 1), (386, 24), (389, 2), (391, 1), (392, 1), (394, 1), (397, 1), (402, 1), (406, 1), (409, 3), (414, 1), (419, 4), (429, 3), (433, 1), (451, 3), (457, 1), (460, 1), (464, 1), (476, 1), (488, 4), (489, 1), (496, 1), (522, 1), (524, 1), (544, 1), (550, 1), (583, 2), (590, 2), (591, 1), (594, 1), (598, 2), (606, 1), (607, 1), (608, 1), (610, 1), (614, 1), (616, 2), (619, 1), (633, 1), (645, 1), (646, 1), (650, 3), (654, 1), (655, 2), (656, 1), (661, 1), (672, 2), (682, 1), (698, 2), (700, 1), (701, 24), (709, 1), (711, 1), (722, 2), (728, 3), (736, 1), (738, 1), (758, 4), (760, 1), (767, 1), (770, 1), (773, 1), (778, 1), (785, 1), (790, 2), (799, 1), (803, 1), (804, 1), (805, 1), (826, 2), (838, 2), (845, 2), (850, 1), (863, 1), (869, 2), (872, 2), (880, 1), (894, 2), (901, 1), (915, 2), (919, 2), (921, 1), (922, 2), (923, 1), (924, 1), (932, 4), (935, 1), (948, 1), (958, 1), (959, 4), (963, 1), (976, 1), (978, 1), (987, 1), (988, 1), (994, 1), (1017, 2), (1023, 2), (1024, 1), (1025, 1), (1043, 1), (1050, 1), (1060, 1), (1063, 1), (1076, 1), (1104, 1), (1110, 1), (1130, 1), (1133, 1), (1144, 1), (1152, 2), (1168, 1), (1186, 1), (1206, 4), (1209, 1), (1214, 1), (1216, 2), (1220, 1), (1222, 1), (1230, 1), (1232, 1), (1235, 2), (1237, 3), (1247, 1), (1254, 3), (1260, 1), (1262, 2), (1267, 1), (1274, 1), (1305, 1), (1317, 1), (1325, 1), (1329, 1), (1352, 2), (1374, 1), (1383, 2), (1388, 2), (1437, 1), (1448, 1), (1451, 1), (1480, 1), (1503, 1), (1513, 1), (1559, 1), (1586, 1), (1622, 1), (1659, 1), (1668, 1), (1672, 1), (1720, 2), (1753, 1), (1764, 1), (1777, 1), (1780, 3), (1785, 1), (1801, 1), (1804, 1), (1808, 1), (1811, 1), (1817, 1), (1826, 3), (1855, 1), (1878, 4), (1879, 1), (1897, 1), (1915, 1), (1925, 1), (1933, 3), (1940, 1), (1977, 1), (2000, 1), (2001, 2), (2002, 2), (2003, 1), (2004, 1), (2005, 1), (2006, 1), (2007, 1), (2008, 1), (2009, 2), (2010, 1), (2011, 1), (2012, 1), (2013, 1), (2014, 1), (2015, 1), (2016, 1), (2017, 1), (2018, 1), (2019, 1), (2020, 2), (2021, 1), (2022, 2), (2023, 1), (2024, 1), (2025, 1), (2026, 2), (2027, 1), (2028, 1), (2029, 1), (2030, 1), (2031, 1), (2032, 1), (2033, 1), (2034, 1), (2035, 1), (2036, 1), (2037, 1), (2038, 1), (2039, 1), (2040, 1), (2041, 1), (2042, 3), (2043, 1), (2044, 1), (2045, 1), (2046, 1), (2047, 1), (2048, 1), (2049, 1), (2050, 1), (2051, 1), (2052, 1), (2053, 1), (2054, 1), (2055, 1), (2056, 1), (2057, 2), (2058, 1), (2059, 1), (2060, 1), (2061, 1), (2062, 1), (2063, 2), (2064, 1), (2065, 1), (2066, 2), (2067, 2), (2068, 1), (2069, 1), (2070, 1), (2071, 2), (2072, 1), (2073, 1), (2074, 1), (2075, 3), (2076, 1), (2077, 2), (2078, 2), (2079, 1), (2080, 1), (2081, 1), (2082, 1), (2083, 1), (2084, 5), (2085, 1), (2086, 1), (2087, 1), (2088, 1), (2089, 1), (2090, 1), (2091, 1), (2092, 1), (2093, 2), (2094, 1), (2095, 1), (2096, 1), (2097, 1), (2098, 1), (2099, 1), (2100, 1), (2101, 1), (2102, 1), (2103, 1), (2104, 1), (2105, 1), (2106, 1), (2107, 1), (2108, 1), (2109, 1), (2110, 1), (2111, 2), (2112, 1), (2113, 1), (2114, 1), (2115, 1), (2116, 1), (2117, 1), (2118, 1), (2119, 1), (2120, 1), (2121, 2), (2122, 2), (2123, 1), (2124, 1), (2125, 2), (2126, 1), (2127, 1), (2128, 1), (2129, 2), (2130, 1), (2131, 1), (2132, 1), (2133, 1), (2134, 1), (2135, 2), (2136, 1), (2137, 1), (2138, 1), (2139, 1), (2140, 1), (2141, 1), (2142, 1), (2143, 1), (2144, 1), (2145, 1), (2146, 1), (2147, 1), (2148, 8)], [(14, 1), (15, 2), (22, 1), (24, 1), (32, 1), (34, 8), (41, 1), (45, 1), (48, 1), (51, 1), (69, 1), (74, 2), (76, 1), (79, 1), (87, 1), (93, 1), (97, 1), (98, 1), (99, 1), (107, 2), (111, 1), (112, 1), (115, 2), (117, 1), (121, 1), (132, 1), (141, 1), (145, 1), (150, 4), (162, 1), (164, 1), (166, 1), (167, 1), (170, 2), (176, 1), (189, 6), (191, 2), (200, 1), (202, 1), (205, 1), (217, 1), (220, 1), (222, 2), (227, 2), (232, 2), (234, 2), (240, 1), (241, 2), (245, 1), (250, 2), (251, 7), (256, 2), (258, 1), (261, 8), (262, 2), (263, 1), (268, 1), (271, 2), (281, 1), (282, 3), (283, 1), (287, 1), (288, 2), (303, 1), (305, 1), (318, 2), (321, 11), (326, 2), (329, 1), (338, 1), (346, 1), (354, 2), (359, 1), (367, 1), (373, 2), (374, 1), (376, 12), (379, 1), (386, 9), (388, 1), (389, 1), (391, 1), (394, 1), (395, 1), (406, 2), (418, 1), (419, 3), (420, 4), (424, 1), (433, 1), (450, 1), (455, 1), (458, 1), (461, 1), (462, 11), (463, 2), (466, 1), (472, 1), (478, 1), (480, 1), (481, 1), (486, 1), (489, 1), (491, 1), (495, 1), (497, 1), (503, 1), (504, 4), (506, 1), (508, 1), (513, 1), (515, 1), (522, 1), (536, 1), (542, 1), (543, 1), (544, 1), (546, 1), (550, 1), (560, 1), (572, 1), (574, 1), (576, 1), (580, 2), (582, 1), (591, 2), (592, 8), (598, 1), (599, 1), (600, 1), (601, 1), (608, 1), (610, 1), (613, 1), (629, 1), (630, 1), (632, 3), (642, 1), (643, 1), (645, 2), (647, 1), (654, 2), (660, 2), (661, 1), (670, 1), (671, 3), (672, 1), (673, 1), (680, 2), (711, 1), (720, 2), (727, 1), (730, 5), (734, 1), (739, 1), (741, 2), (744, 2), (752, 1), (754, 1), (756, 1), (761, 6), (770, 1), (774, 1), (794, 1), (803, 1), (807, 2), (808, 1), (809, 2), (813, 1), (815, 1), (844, 6), (853, 1), (854, 1), (869, 3), (874, 1), (879, 1), (898, 1), (923, 1), (924, 1), (935, 1), (948, 1), (958, 1), (959, 1), (966, 1), (990, 1), (1022, 1), (1024, 1), (1033, 1), (1038, 1), (1048, 2), (1071, 1), (1075, 2), (1159, 1), (1206, 1), (1237, 1), (1245, 1), (1255, 1), (1263, 1), (1272, 1), (1278, 1), (1283, 1), (1291, 1), (1309, 1), (1323, 1), (1326, 1), (1352, 1), (1357, 1), (1361, 1), (1385, 1), (1405, 1), (1426, 1), (1429, 1), (1438, 1), (1451, 1), (1516, 1), (1541, 1), (1591, 1), (1597, 1), (1598, 1), (1599, 1), (1619, 2), (1622, 1), (1629, 1), (1640, 1), (1645, 1), (1663, 1), (1669, 2), (1670, 1), (1676, 1), (1682, 1), (1698, 1), (1709, 1), (1711, 1), (1722, 1), (1733, 1), (1794, 1), (1802, 1), (1817, 2), (1847, 1), (1909, 1), (1914, 1), (1973, 1), (1976, 2), (1991, 1), (2009, 1), (2017, 1), (2040, 1), (2077, 1), (2134, 1), (2149, 1), (2150, 1), (2151, 1), (2152, 1), (2153, 1), (2154, 1), (2155, 1), (2156, 1), (2157, 1), (2158, 1), (2159, 1), (2160, 1), (2161, 1), (2162, 1), (2163, 1), (2164, 1), (2165, 1), (2166, 1), (2167, 1), (2168, 1), (2169, 1), (2170, 1), (2171, 1), (2172, 2), (2173, 2), (2174, 1), (2175, 1), (2176, 3), (2177, 1), (2178, 1), (2179, 1), (2180, 1), (2181, 1), (2182, 1), (2183, 1), (2184, 5), (2185, 2), (2186, 1), (2187, 1), (2188, 1), (2189, 1), (2190, 1), (2191, 1), (2192, 1), (2193, 1), (2194, 1), (2195, 1), (2196, 1), (2197, 1), (2198, 1), (2199, 1), (2200, 1), (2201, 1), (2202, 1), (2203, 1), (2204, 1), (2205, 1), (2206, 1), (2207, 1), (2208, 2), (2209, 1), (2210, 1), (2211, 2), (2212, 1), (2213, 1), (2214, 1), (2215, 1), (2216, 1), (2217, 1), (2218, 1), (2219, 1), (2220, 6), (2221, 1), (2222, 1), (2223, 1), (2224, 1), (2225, 1), (2226, 1), (2227, 1), (2228, 1), (2229, 1), (2230, 1), (2231, 1), (2232, 1), (2233, 1), (2234, 1), (2235, 1), (2236, 1), (2237, 1), (2238, 1), (2239, 1), (2240, 1), (2241, 1), (2242, 1), (2243, 1), (2244, 1), (2245, 1), (2246, 1), (2247, 1), (2248, 1), (2249, 2), (2250, 1), (2251, 1), (2252, 1), (2253, 1), (2254, 1), (2255, 1), (2256, 1), (2257, 1), (2258, 1), (2259, 3), (2260, 2), (2261, 1), (2262, 1), (2263, 1), (2264, 1), (2265, 1), (2266, 1), (2267, 1), (2268, 1), (2269, 1), (2270, 1), (2271, 1), (2272, 3), (2273, 1), (2274, 1), (2275, 1), (2276, 1), (2277, 1), (2278, 2)], [(5, 1), (9, 1), (13, 1), (14, 2), (25, 3), (34, 1), (37, 2), (45, 1), (51, 2), (55, 2), (56, 1), (68, 3), (79, 2), (85, 3), (88, 1), (97, 2), (103, 2), (107, 4), (112, 1), (119, 1), (127, 1), (133, 3), (140, 1), (142, 3), (145, 2), (150, 2), (152, 1), (157, 1), (158, 1), (162, 3), (164, 9), (186, 2), (187, 10), (200, 1), (217, 3), (222, 2), (224, 2), (227, 8), (229, 1), (232, 4), (240, 1), (241, 2), (247, 1), (248, 1), (250, 2), (251, 27), (259, 1), (261, 3), (263, 2), (264, 1), (268, 1), (271, 3), (282, 6), (296, 1), (305, 1), (308, 1), (311, 2), (317, 2), (321, 24), (329, 1), (330, 2), (344, 3), (353, 2), (356, 2), (359, 1), (361, 1), (362, 2), (364, 1), (369, 4), (371, 3), (372, 3), (373, 4), (376, 5), (394, 2), (396, 1), (406, 7), (409, 1), (412, 1), (416, 1), (418, 4), (419, 3), (420, 3), (436, 2), (438, 1), (442, 1), (444, 6), (446, 1), (449, 1), (452, 1), (456, 1), (458, 1), (464, 1), (470, 1), (487, 1), (505, 1), (506, 1), (518, 1), (522, 1), (524, 1), (528, 1), (531, 4), (536, 1), (538, 1), (541, 1), (543, 1), (544, 2), (545, 1), (546, 1), (550, 1), (559, 3), (560, 2), (566, 1), (579, 2), (590, 1), (591, 2), (592, 1), (593, 1), (594, 2), (595, 1), (604, 1), (610, 2), (611, 1), (614, 1), (632, 1), (654, 1), (657, 2), (667, 2), (672, 3), (679, 1), (684, 1), (685, 1), (686, 2), (690, 3), (692, 1), (708, 1), (709, 1), (720, 1), (725, 5), (726, 2), (727, 5), (731, 1), (737, 1), (738, 3), (745, 7), (758, 3), (770, 4), (775, 3), (784, 1), (792, 1), (793, 3), (803, 1), (816, 1), (828, 1), (845, 1), (849, 1), (850, 2), (863, 2), (866, 3), (869, 1), (872, 7), (874, 1), (879, 1), (880, 1), (894, 3), (898, 1), (899, 1), (902, 1), (911, 2), (922, 2), (932, 1), (947, 1), (948, 1), (958, 2), (959, 2), (960, 1), (967, 1), (971, 1), (979, 2), (981, 1), (983, 1), (989, 1), (991, 1), (1020, 1), (1024, 1), (1038, 2), (1052, 4), (1059, 1), (1068, 1), (1072, 2), (1075, 2), (1079, 1), (1111, 3), (1115, 3), (1116, 1), (1134, 1), (1142, 4), (1146, 2), (1149, 1), (1157, 2), (1162, 1), (1164, 1), (1167, 1), (1175, 2), (1178, 1), (1182, 4), (1183, 1), (1204, 1), (1205, 1), (1206, 2), (1209, 2), (1213, 4), (1215, 2), (1219, 2), (1237, 1), (1239, 7), (1240, 1), (1262, 2), (1263, 3), (1265, 1), (1273, 2), (1275, 1), (1278, 1), (1283, 1), (1290, 1), (1292, 1), (1298, 1), (1299, 2), (1301, 8), (1307, 1), (1309, 1), (1315, 1), (1317, 1), (1326, 1), (1327, 1), (1340, 1), (1351, 1), (1352, 2), (1354, 7), (1375, 1), (1383, 2), (1385, 4), (1429, 2), (1430, 1), (1438, 1), (1446, 1), (1451, 1), (1470, 1), (1473, 1), (1480, 1), (1504, 2), (1511, 4), (1513, 2), (1518, 1), (1544, 1), (1548, 3), (1567, 1), (1584, 4), (1617, 1), (1626, 1), (1629, 1), (1657, 3), (1668, 1), (1670, 2), (1673, 3), (1676, 1), (1680, 1), (1698, 2), (1710, 1), (1725, 1), (1729, 1), (1737, 1), (1748, 1), (1765, 1), (1773, 1), (1775, 1), (1785, 1), (1791, 1), (1807, 1), (1817, 1), (1826, 2), (1839, 1), (1840, 1), (1845, 1), (1847, 3), (1864, 5), (1870, 1), (1877, 1), (1886, 2), (1896, 2), (1899, 1), (1904, 2), (1908, 1), (1934, 1), (1937, 2), (1938, 2), (1940, 1), (1952, 1), (1990, 1), (2027, 1), (2044, 1), (2045, 1), (2052, 1), (2061, 1), (2065, 1), (2069, 1), (2071, 2), (2077, 6), (2089, 1), (2093, 1), (2098, 2), (2100, 1), (2104, 1), (2117, 2), (2127, 1), (2148, 1), (2188, 1), (2212, 1), (2222, 1), (2264, 2), (2275, 1), (2277, 1), (2279, 1), (2280, 1), (2281, 1), (2282, 3), (2283, 1), (2284, 1), (2285, 1), (2286, 1), (2287, 1), (2288, 1), (2289, 1), (2290, 3), (2291, 2), (2292, 1), (2293, 1), (2294, 1), (2295, 1), (2296, 2), (2297, 1), (2298, 1), (2299, 1), (2300, 1), (2301, 1), (2302, 1), (2303, 1), (2304, 2), (2305, 1), (2306, 1), (2307, 1), (2308, 1), (2309, 1), (2310, 2), (2311, 2), (2312, 1), (2313, 1), (2314, 1), (2315, 1), (2316, 1), (2317, 1), (2318, 1), (2319, 1), (2320, 1), (2321, 1), (2322, 1), (2323, 1), (2324, 1), (2325, 1), (2326, 1), (2327, 1), (2328, 1), (2329, 1), (2330, 1), (2331, 1), (2332, 2), (2333, 1), (2334, 1), (2335, 1), (2336, 1), (2337, 1), (2338, 2), (2339, 1), (2340, 1), (2341, 1), (2342, 1), (2343, 1), (2344, 1), (2345, 1), (2346, 1), (2347, 1), (2348, 1), (2349, 1), (2350, 1), (2351, 1), (2352, 1), (2353, 1), (2354, 1), (2355, 1), (2356, 1), (2357, 1), (2358, 1), (2359, 1), (2360, 1), (2361, 1), (2362, 1), (2363, 1), (2364, 1), (2365, 1), (2366, 1), (2367, 1), (2368, 1), (2369, 1), (2370, 1), (2371, 1), (2372, 1), (2373, 2), (2374, 1), (2375, 1), (2376, 1), (2377, 1), (2378, 1), (2379, 1), (2380, 1), (2381, 1), (2382, 1), (2383, 1), (2384, 1), (2385, 1), (2386, 1), (2387, 1), (2388, 1), (2389, 1), (2390, 1), (2391, 1), (2392, 1), (2393, 1), (2394, 1), (2395, 1), (2396, 1), (2397, 1), (2398, 1), (2399, 1), (2400, 2), (2401, 1), (2402, 1), (2403, 1), (2404, 1), (2405, 1), (2406, 1), (2407, 1), (2408, 1), (2409, 1), (2410, 1), (2411, 29), (2412, 1), (2413, 1), (2414, 1), (2415, 1), (2416, 1), (2417, 1), (2418, 2), (2419, 1), (2420, 2), (2421, 1), (2422, 1), (2423, 1), (2424, 1), (2425, 1), (2426, 2), (2427, 1), (2428, 2), (2429, 1), (2430, 1), (2431, 1), (2432, 1), (2433, 1), (2434, 1), (2435, 1), (2436, 2), (2437, 1), (2438, 1), (2439, 1), (2440, 3), (2441, 1), (2442, 1), (2443, 2), (2444, 1), (2445, 1), (2446, 1), (2447, 1), (2448, 1), (2449, 1), (2450, 1), (2451, 1), (2452, 1), (2453, 1), (2454, 1), (2455, 1), (2456, 1), (2457, 1), (2458, 1), (2459, 1), (2460, 1), (2461, 1), (2462, 1), (2463, 1), (2464, 1), (2465, 1), (2466, 1), (2467, 4), (2468, 1), (2469, 1), (2470, 2), (2471, 1), (2472, 1), (2473, 1), (2474, 1), (2475, 2), (2476, 1), (2477, 2), (2478, 1), (2479, 1), (2480, 1), (2481, 1), (2482, 1), (2483, 1), (2484, 1), (2485, 3), (2486, 1), (2487, 1), (2488, 1), (2489, 1), (2490, 1), (2491, 2), (2492, 1), (2493, 1), (2494, 1), (2495, 1), (2496, 1), (2497, 1), (2498, 1), (2499, 1), (2500, 1), (2501, 1), (2502, 1), (2503, 1), (2504, 1), (2505, 1), (2506, 1), (2507, 1), (2508, 1), (2509, 1), (2510, 1), (2511, 1), (2512, 1), (2513, 1), (2514, 1), (2515, 1)], [(0, 1), (17, 1), (29, 1), (51, 2), (68, 1), (70, 1), (74, 2), (83, 1), (85, 2), (86, 2), (93, 3), (98, 4), (107, 2), (115, 1), (135, 1), (150, 4), (157, 1), (158, 1), (160, 1), (162, 1), (164, 5), (170, 2), (175, 1), (176, 1), (187, 3), (191, 2), (196, 1), (200, 1), (202, 1), (205, 2), (213, 1), (215, 1), (217, 1), (227, 4), (229, 1), (232, 3), (234, 3), (241, 1), (251, 19), (256, 1), (261, 2), (262, 1), (263, 1), (265, 1), (271, 3), (278, 1), (282, 8), (290, 1), (306, 1), (321, 12), (329, 2), (331, 2), (337, 7), (353, 1), (362, 1), (367, 1), (371, 1), (373, 1), (379, 1), (386, 17), (389, 2), (392, 1), (401, 1), (409, 1), (411, 1), (413, 1), (415, 1), (418, 1), (419, 2), (420, 2), (429, 2), (444, 2), (446, 1), (461, 2), (464, 2), (470, 1), (495, 1), (503, 1), (522, 2), (536, 1), (541, 2), (542, 1), (545, 1), (550, 1), (558, 1), (559, 1), (562, 1), (563, 1), (591, 4), (594, 1), (610, 1), (616, 4), (632, 1), (641, 1), (642, 1), (643, 1), (645, 7), (658, 1), (660, 1), (661, 1), (672, 1), (693, 1), (701, 6), (711, 1), (720, 1), (722, 1), (726, 3), (727, 1), (729, 1), (730, 3), (745, 1), (759, 1), (762, 7), (770, 2), (774, 1), (778, 2), (784, 1), (788, 2), (837, 1), (838, 5), (844, 1), (872, 1), (874, 1), (875, 4), (900, 2), (902, 1), (919, 1), (923, 2), (932, 1), (934, 1), (935, 1), (953, 4), (959, 1), (963, 1), (966, 1), (972, 2), (991, 2), (1011, 1), (1015, 1), (1016, 2), (1017, 1), (1023, 1), (1024, 2), (1050, 1), (1072, 1), (1110, 1), (1130, 3), (1142, 1), (1154, 1), (1169, 1), (1177, 1), (1215, 8), (1216, 2), (1219, 1), (1222, 2), (1239, 1), (1241, 2), (1246, 1), (1257, 1), (1262, 1), (1263, 2), (1291, 1), (1300, 1), (1301, 1), (1354, 2), (1355, 1), (1357, 1), (1374, 2), (1390, 1), (1438, 1), (1473, 1), (1510, 2), (1511, 1), (1513, 1), (1522, 2), (1530, 2), (1612, 2), (1614, 2), (1631, 1), (1653, 1), (1657, 3), (1668, 1), (1714, 1), (1721, 3), (1748, 2), (1806, 1), (1815, 1), (1826, 1), (1827, 1), (1832, 1), (1847, 3), (1911, 1), (1914, 1), (1938, 1), (1957, 2), (1976, 1), (2009, 1), (2027, 1), (2065, 3), (2073, 2), (2094, 1), (2110, 2), (2133, 1), (2144, 1), (2145, 1), (2164, 1), (2210, 3), (2218, 1), (2275, 1), (2282, 1), (2293, 1), (2339, 1), (2398, 1), (2410, 1), (2416, 2), (2429, 1), (2459, 1), (2502, 4), (2512, 1), (2514, 1), (2516, 1), (2517, 1), (2518, 1), (2519, 1), (2520, 2), (2521, 10), (2522, 1), (2523, 1), (2524, 1), (2525, 1), (2526, 1), (2527, 1), (2528, 1), (2529, 1), (2530, 1), (2531, 2), (2532, 1), (2533, 1), (2534, 1), (2535, 1), (2536, 1), (2537, 1), (2538, 1), (2539, 1), (2540, 2), (2541, 1), (2542, 1), (2543, 1), (2544, 1), (2545, 1), (2546, 1), (2547, 1), (2548, 1), (2549, 1), (2550, 1), (2551, 2), (2552, 1), (2553, 1), (2554, 1), (2555, 1), (2556, 1), (2557, 1), (2558, 1), (2559, 1), (2560, 1), (2561, 1), (2562, 1), (2563, 1), (2564, 1), (2565, 2), (2566, 1), (2567, 2), (2568, 1), (2569, 1), (2570, 1), (2571, 1), (2572, 1), (2573, 2), (2574, 1), (2575, 1), (2576, 1), (2577, 1), (2578, 1), (2579, 1), (2580, 2), (2581, 1), (2582, 1), (2583, 1), (2584, 1), (2585, 1), (2586, 1), (2587, 1), (2588, 1), (2589, 1), (2590, 1), (2591, 5), (2592, 1), (2593, 1), (2594, 1), (2595, 1), (2596, 1), (2597, 1), (2598, 1), (2599, 1), (2600, 1), (2601, 1), (2602, 1), (2603, 1), (2604, 1), (2605, 1), (2606, 1), (2607, 1), (2608, 1), (2609, 2), (2610, 1), (2611, 1), (2612, 1)], [(4, 1), (12, 2), (24, 2), (37, 1), (51, 1), (104, 2), (107, 1), (150, 1), (217, 3), (234, 1), (250, 2), (268, 3), (271, 1), (282, 2), (283, 2), (321, 2), (350, 1), (376, 4), (419, 1), (420, 5), (474, 1), (528, 3), (548, 1), (567, 1), (580, 1), (584, 1), (612, 2), (632, 1), (690, 1), (707, 1), (738, 1), (751, 1), (755, 3), (757, 1), (834, 1), (898, 1), (921, 2), (922, 1), (956, 1), (961, 1), (965, 1), (969, 1), (981, 3), (983, 1), (1039, 1), (1075, 1), (1092, 4), (1117, 1), (1206, 1), (1226, 1), (1252, 1), (1255, 1), (1259, 1), (1273, 2), (1292, 1), (1361, 1), (1404, 1), (1419, 1), (1456, 1), (1461, 1), (1513, 1), (1598, 1), (1604, 1), (1607, 2), (1628, 1), (1657, 1), (1663, 2), (1669, 3), (1676, 1), (1715, 2), (1716, 3), (1763, 1), (1914, 1), (1945, 1), (2276, 1), (2458, 1), (2473, 3), (2498, 2), (2534, 6), (2613, 1), (2614, 1), (2615, 1), (2616, 1), (2617, 1), (2618, 1), (2619, 1), (2620, 1), (2621, 1), (2622, 1), (2623, 1), (2624, 1), (2625, 1), (2626, 1), (2627, 1), (2628, 3), (2629, 1), (2630, 1), (2631, 1), (2632, 1), (2633, 1), (2634, 1), (2635, 1), (2636, 2), (2637, 1), (2638, 1), (2639, 1), (2640, 1), (2641, 1), (2642, 1), (2643, 4), (2644, 1), (2645, 2), (2646, 1), (2647, 1), (2648, 1), (2649, 1), (2650, 1), (2651, 1), (2652, 1), (2653, 3), (2654, 1)], [(0, 1), (3, 2), (12, 2), (15, 2), (18, 5), (22, 2), (24, 1), (25, 3), (32, 1), (35, 1), (45, 2), (50, 1), (62, 1), (76, 1), (83, 1), (86, 1), (88, 9), (89, 1), (97, 1), (112, 1), (122, 1), (133, 1), (137, 1), (138, 1), (150, 1), (188, 1), (190, 1), (193, 2), (200, 5), (217, 1), (229, 1), (232, 1), (234, 1), (240, 1), (250, 1), (251, 2), (253, 3), (256, 2), (262, 1), (263, 1), (268, 1), (287, 1), (290, 4), (297, 6), (319, 1), (321, 8), (326, 1), (331, 1), (332, 2), (338, 4), (350, 1), (354, 1), (355, 1), (362, 1), (368, 16), (372, 1), (376, 2), (378, 1), (394, 2), (420, 3), (445, 1), (469, 11), (473, 1), (481, 1), (487, 1), (506, 1), (511, 1), (523, 1), (550, 1), (558, 1), (580, 1), (584, 1), (585, 1), (594, 1), (598, 1), (610, 1), (613, 1), (614, 2), (620, 1), (621, 2), (632, 1), (654, 1), (660, 1), (672, 2), (679, 1), (728, 2), (736, 2), (738, 2), (739, 1), (758, 1), (770, 1), (803, 2), (804, 1), (817, 3), (826, 1), (877, 1), (886, 1), (889, 1), (892, 1), (902, 1), (922, 1), (943, 1), (947, 1), (959, 1), (960, 1), (965, 2), (983, 1), (991, 2), (1011, 1), (1030, 3), (1050, 1), (1071, 1), (1075, 1), (1088, 1), (1104, 1), (1142, 1), (1159, 1), (1203, 2), (1209, 1), (1227, 1), (1241, 3), (1265, 2), (1326, 2), (1352, 1), (1354, 1), (1360, 1), (1419, 1), (1440, 1), (1442, 1), (1505, 1), (1546, 2), (1594, 2), (1612, 1), (1642, 1), (1670, 1), (1674, 1), (1679, 2), (1681, 2), (1689, 7), (1732, 3), (1756, 1), (1764, 1), (1783, 1), (1800, 2), (1806, 2), (1826, 1), (1837, 1), (1876, 1), (1907, 1), (1909, 1), (1990, 1), (2002, 1), (2013, 1), (2027, 1), (2075, 2), (2083, 1), (2104, 1), (2105, 1), (2106, 1), (2113, 1), (2115, 1), (2259, 1), (2282, 1), (2310, 2), (2502, 1), (2517, 1), (2551, 1), (2614, 1), (2617, 1), (2655, 1), (2656, 1), (2657, 1), (2658, 1), (2659, 9), (2660, 1), (2661, 4), (2662, 1), (2663, 2), (2664, 4), (2665, 1), (2666, 1), (2667, 1), (2668, 3), (2669, 1), (2670, 1), (2671, 3), (2672, 1), (2673, 4), (2674, 2), (2675, 2), (2676, 1), (2677, 1), (2678, 1), (2679, 1), (2680, 1), (2681, 3), (2682, 1), (2683, 1), (2684, 1), (2685, 1), (2686, 1), (2687, 1), (2688, 1), (2689, 1), (2690, 1), (2691, 1), (2692, 1), (2693, 1), (2694, 4), (2695, 2), (2696, 1), (2697, 3), (2698, 3), (2699, 1), (2700, 1), (2701, 1), (2702, 1), (2703, 1), (2704, 1), (2705, 2), (2706, 1), (2707, 1), (2708, 1), (2709, 1), (2710, 12), (2711, 1), (2712, 2), (2713, 2), (2714, 4), (2715, 1), (2716, 1), (2717, 2), (2718, 1), (2719, 2), (2720, 1), (2721, 1), (2722, 1), (2723, 5), (2724, 1), (2725, 3), (2726, 4), (2727, 1), (2728, 2), (2729, 1), (2730, 1), (2731, 1), (2732, 1), (2733, 1), (2734, 1), (2735, 1), (2736, 9), (2737, 1), (2738, 1), (2739, 1), (2740, 1), (2741, 1), (2742, 1), (2743, 1), (2744, 1), (2745, 2), (2746, 1), (2747, 1), (2748, 1), (2749, 2)], [(0, 1), (3, 1), (5, 1), (18, 3), (25, 2), (29, 2), (40, 1), (50, 1), (51, 2), (54, 2), (62, 3), (69, 2), (77, 1), (81, 3), (93, 1), (97, 2), (127, 1), (133, 3), (136, 1), (137, 1), (138, 1), (140, 1), (144, 3), (150, 3), (162, 1), (164, 1), (168, 12), (170, 2), (174, 2), (176, 4), (183, 2), (187, 1), (188, 1), (210, 1), (212, 3), (217, 4), (222, 1), (229, 2), (234, 5), (236, 1), (241, 1), (250, 2), (251, 16), (256, 5), (258, 1), (259, 2), (270, 4), (271, 5), (275, 2), (282, 4), (293, 1), (300, 3), (309, 2), (314, 1), (317, 1), (321, 27), (326, 1), (330, 1), (331, 1), (337, 2), (346, 1), (350, 1), (354, 17), (356, 2), (359, 1), (374, 4), (376, 2), (378, 3), (388, 1), (391, 5), (394, 2), (401, 2), (406, 1), (407, 1), (409, 1), (411, 1), (420, 3), (424, 1), (445, 6), (446, 1), (453, 1), (469, 4), (471, 1), (490, 1), (495, 1), (507, 1), (534, 2), (550, 1), (560, 10), (564, 1), (579, 1), (582, 1), (591, 3), (593, 1), (594, 1), (598, 2), (608, 1), (612, 2), (621, 1), (642, 1), (660, 1), (672, 2), (673, 1), (675, 1), (683, 1), (695, 1), (713, 1), (715, 1), (716, 1), (721, 1), (733, 1), (736, 2), (738, 3), (744, 2), (748, 1), (758, 2), (770, 1), (773, 3), (774, 1), (778, 1), (780, 1), (789, 3), (869, 2), (874, 4), (883, 1), (884, 7), (886, 1), (887, 1), (896, 1), (897, 1), (898, 1), (907, 1), (921, 2), (923, 1), (934, 1), (948, 1), (949, 1), (950, 1), (958, 1), (962, 1), (963, 1), (965, 1), (969, 1), (971, 1), (976, 4), (983, 4), (987, 1), (991, 2), (993, 1), (1004, 1), (1022, 1), (1030, 3), (1033, 1), (1038, 1), (1050, 1), (1053, 1), (1092, 11), (1112, 1), (1158, 1), (1169, 1), (1179, 1), (1186, 1), (1213, 1), (1217, 1), (1219, 1), (1245, 1), (1262, 2), (1267, 1), (1278, 10), (1300, 1), (1305, 1), (1320, 1), (1323, 1), (1343, 1), (1361, 1), (1367, 1), (1372, 1), (1375, 1), (1379, 1), (1402, 1), (1420, 1), (1424, 1), (1426, 1), (1438, 1), (1439, 1), (1445, 6), (1447, 1), (1468, 2), (1471, 1), (1487, 1), (1490, 1), (1502, 1), (1505, 1), (1511, 1), (1518, 3), (1520, 1), (1530, 2), (1533, 1), (1562, 1), (1586, 1), (1596, 5), (1597, 1), (1602, 3), (1609, 1), (1627, 2), (1655, 5), (1657, 1), (1660, 1), (1663, 1), (1669, 4), (1680, 1), (1708, 2), (1720, 1), (1721, 2), (1734, 1), (1772, 1), (1782, 1), (1783, 1), (1798, 1), (1802, 1), (1806, 1), (1807, 1), (1817, 1), (1826, 1), (1839, 2), (1847, 3), (1880, 1), (1896, 1), (1904, 1), (1934, 1), (1937, 1), (1940, 1), (1966, 1), (1976, 3), (1988, 1), (2076, 2), (2077, 1), (2088, 1), (2108, 1), (2155, 1), (2188, 1), (2195, 1), (2207, 1), (2212, 1), (2288, 1), (2377, 1), (2408, 1), (2479, 1), (2515, 1), (2539, 1), (2546, 1), (2562, 15), (2565, 1), (2577, 2), (2586, 6), (2603, 3), (2605, 1), (2629, 1), (2631, 1), (2680, 1), (2725, 4), (2750, 2), (2751, 3), (2752, 2), (2753, 1), (2754, 1), (2755, 1), (2756, 2), (2757, 1), (2758, 1), (2759, 1), (2760, 1), (2761, 3), (2762, 2), (2763, 3), (2764, 1), (2765, 1), (2766, 2), (2767, 1), (2768, 1), (2769, 5), (2770, 1), (2771, 1), (2772, 2), (2773, 1), (2774, 1), (2775, 1), (2776, 1), (2777, 1), (2778, 4), (2779, 2), (2780, 2), (2781, 1), (2782, 1), (2783, 1), (2784, 1), (2785, 1), (2786, 1), (2787, 1), (2788, 1), (2789, 2), (2790, 1), (2791, 1), (2792, 1), (2793, 1), (2794, 1), (2795, 1), (2796, 1), (2797, 1), (2798, 2), (2799, 1), (2800, 1), (2801, 1), (2802, 1), (2803, 1), (2804, 1), (2805, 1), (2806, 1), (2807, 1), (2808, 2), (2809, 1), (2810, 4), (2811, 1), (2812, 1), (2813, 1), (2814, 1), (2815, 1), (2816, 1), (2817, 1), (2818, 1), (2819, 24), (2820, 1), (2821, 6), (2822, 2), (2823, 1), (2824, 1), (2825, 1), (2826, 1), (2827, 1), (2828, 1), (2829, 1), (2830, 1), (2831, 1), (2832, 1), (2833, 1), (2834, 1), (2835, 1), (2836, 1), (2837, 1), (2838, 1), (2839, 2), (2840, 1), (2841, 4), (2842, 1), (2843, 4), (2844, 1), (2845, 1), (2846, 1), (2847, 2), (2848, 1), (2849, 1), (2850, 3), (2851, 1), (2852, 1), (2853, 1), (2854, 1), (2855, 1), (2856, 1), (2857, 3), (2858, 2), (2859, 2), (2860, 2), (2861, 1), (2862, 2), (2863, 1), (2864, 1), (2865, 1), (2866, 1), (2867, 1), (2868, 1), (2869, 2), (2870, 1), (2871, 1), (2872, 1), (2873, 1), (2874, 1), (2875, 1), (2876, 1), (2877, 1), (2878, 1), (2879, 1), (2880, 2), (2881, 1), (2882, 2), (2883, 1), (2884, 1), (2885, 10), (2886, 1), (2887, 5), (2888, 1), (2889, 1), (2890, 1), (2891, 1), (2892, 1), (2893, 1), (2894, 1), (2895, 1), (2896, 3), (2897, 1), (2898, 1), (2899, 1), (2900, 1), (2901, 2), (2902, 1), (2903, 1), (2904, 1), (2905, 1), (2906, 1), (2907, 1), (2908, 1), (2909, 2), (2910, 1), (2911, 1), (2912, 1), (2913, 3), (2914, 1), (2915, 1), (2916, 1), (2917, 2), (2918, 1), (2919, 1), (2920, 1), (2921, 1), (2922, 1), (2923, 10), (2924, 1), (2925, 1), (2926, 1), (2927, 1), (2928, 1), (2929, 1), (2930, 1), (2931, 1), (2932, 1), (2933, 1), (2934, 1), (2935, 2), (2936, 1), (2937, 4), (2938, 1), (2939, 1), (2940, 1), (2941, 1), (2942, 1)], [(0, 1), (15, 2), (17, 3), (18, 2), (24, 1), (25, 3), (30, 1), (35, 1), (49, 2), (51, 3), (61, 2), (64, 2), (68, 1), (69, 3), (74, 2), (77, 2), (81, 1), (83, 1), (87, 1), (88, 1), (97, 8), (98, 2), (99, 1), (107, 7), (110, 1), (118, 1), (127, 1), (137, 10), (140, 1), (144, 1), (145, 1), (149, 1), (150, 8), (158, 1), (160, 1), (164, 2), (168, 3), (170, 1), (176, 2), (180, 3), (183, 1), (188, 1), (189, 9), (196, 1), (200, 4), (202, 1), (217, 1), (218, 1), (222, 1), (227, 2), (229, 2), (232, 2), (234, 2), (248, 2), (250, 1), (251, 23), (261, 2), (268, 1), (271, 1), (279, 1), (282, 2), (287, 5), (288, 1), (291, 1), (292, 1), (297, 2), (300, 2), (305, 1), (317, 2), (321, 7), (325, 1), (327, 1), (329, 1), (338, 2), (344, 1), (349, 2), (354, 3), (356, 3), (364, 1), (372, 1), (376, 2), (378, 2), (382, 1), (383, 2), (386, 16), (391, 1), (394, 3), (401, 1), (406, 4), (409, 2), (412, 1), (417, 1), (419, 4), (426, 1), (428, 13), (429, 1), (436, 1), (470, 3), (489, 1), (499, 1), (503, 1), (504, 3), (506, 2), (511, 1), (535, 1), (538, 1), (541, 1), (544, 2), (565, 1), (584, 2), (585, 1), (586, 1), (594, 2), (598, 1), (604, 1), (611, 1), (614, 1), (622, 1), (624, 10), (632, 2), (643, 3), (645, 12), (650, 2), (655, 1), (659, 1), (672, 1), (673, 1), (674, 1), (680, 3), (681, 1), (684, 1), (703, 1), (714, 1), (719, 1), (720, 4), (748, 1), (755, 1), (758, 3), (769, 1), (770, 1), (771, 2), (773, 4), (775, 2), (776, 1), (788, 1), (807, 3), (808, 1), (838, 1), (840, 2), (845, 1), (850, 1), (863, 2), (874, 4), (875, 2), (876, 1), (883, 1), (887, 1), (889, 1), (892, 1), (899, 1), (905, 1), (919, 8), (921, 7), (922, 2), (931, 2), (947, 2), (952, 2), (957, 1), (965, 2), (969, 1), (976, 1), (983, 1), (991, 1), (993, 1), (994, 1), (1004, 1), (1016, 2), (1017, 1), (1023, 1), (1024, 4), (1030, 1), (1037, 1), (1047, 1), (1049, 1), (1092, 1), (1118, 3), (1130, 1), (1176, 1), (1199, 1), (1217, 1), (1237, 1), (1255, 2), (1262, 1), (1267, 5), (1273, 1), (1291, 1), (1311, 1), (1326, 2), (1352, 1), (1366, 1), (1379, 1), (1406, 1), (1437, 1), (1440, 4), (1442, 1), (1464, 1), (1474, 1), (1493, 1), (1511, 1), (1513, 2), (1518, 1), (1544, 1), (1562, 1), (1574, 1), (1597, 1), (1599, 1), (1624, 1), (1640, 5), (1651, 1), (1655, 1), (1663, 1), (1676, 3), (1677, 1), (1693, 1), (1704, 1), (1711, 2), (1753, 1), (1766, 1), (1773, 2), (1785, 4), (1804, 1), (1808, 1), (1817, 1), (1826, 2), (1827, 1), (1847, 3), (1873, 1), (1883, 1), (1886, 1), (1887, 1), (1909, 1), (1951, 4), (1966, 2), (1970, 1), (2005, 1), (2014, 1), (2015, 1), (2033, 1), (2055, 1), (2090, 1), (2127, 2), (2183, 1), (2202, 2), (2246, 2), (2271, 2), (2272, 3), (2275, 1), (2310, 2), (2452, 1), (2468, 1), (2479, 1), (2515, 2), (2539, 1), (2545, 1), (2551, 3), (2562, 1), (2609, 1), (2638, 1), (2677, 1), (2723, 1), (2726, 1), (2731, 1), (2735, 1), (2769, 1), (2788, 1), (2812, 1), (2836, 1), (2855, 1), (2864, 1), (2935, 1), (2943, 1), (2944, 2), (2945, 1), (2946, 3), (2947, 1), (2948, 1), (2949, 1), (2950, 1), (2951, 1), (2952, 1), (2953, 1), (2954, 1), (2955, 2), (2956, 1), (2957, 1), (2958, 1), (2959, 1), (2960, 1), (2961, 1), (2962, 1), (2963, 1), (2964, 1), (2965, 1), (2966, 1), (2967, 1), (2968, 2), (2969, 1), (2970, 1), (2971, 1), (2972, 1), (2973, 1), (2974, 1), (2975, 1), (2976, 1), (2977, 1), (2978, 1), (2979, 1), (2980, 1), (2981, 1), (2982, 1), (2983, 1), (2984, 1), (2985, 1), (2986, 1), (2987, 1), (2988, 1), (2989, 1), (2990, 1), (2991, 1), (2992, 1), (2993, 1), (2994, 1), (2995, 1), (2996, 1), (2997, 1), (2998, 1), (2999, 1), (3000, 1), (3001, 1), (3002, 1), (3003, 1), (3004, 1), (3005, 1), (3006, 1), (3007, 1), (3008, 1), (3009, 1), (3010, 1), (3011, 1), (3012, 1), (3013, 1), (3014, 1), (3015, 1), (3016, 1), (3017, 1), (3018, 1), (3019, 2), (3020, 1), (3021, 1), (3022, 1), (3023, 1), (3024, 1), (3025, 1), (3026, 1), (3027, 1), (3028, 1), (3029, 1), (3030, 1), (3031, 2), (3032, 1), (3033, 1), (3034, 1), (3035, 1)], [(13, 1), (22, 1), (25, 2), (29, 1), (30, 3), (33, 1), (37, 1), (49, 1), (50, 2), (51, 3), (54, 1), (56, 1), (61, 1), (64, 1), (68, 3), (74, 1), (78, 4), (79, 1), (83, 1), (85, 3), (94, 1), (97, 2), (98, 3), (99, 2), (107, 1), (111, 2), (120, 1), (125, 1), (133, 1), (136, 1), (140, 1), (144, 1), (145, 1), (150, 5), (157, 2), (162, 1), (164, 2), (166, 1), (174, 1), (175, 1), (176, 1), (178, 1), (180, 1), (181, 1), (191, 1), (199, 1), (204, 2), (205, 1), (206, 1), (207, 1), (210, 1), (213, 3), (217, 1), (218, 1), (222, 2), (227, 4), (229, 3), (234, 5), (240, 2), (241, 1), (248, 2), (258, 3), (259, 5), (260, 2), (261, 4), (262, 1), (263, 1), (266, 1), (268, 1), (270, 2), (271, 10), (279, 2), (289, 1), (292, 2), (308, 1), (309, 1), (311, 1), (318, 1), (329, 2), (330, 2), (331, 1), (332, 1), (341, 1), (344, 2), (345, 2), (356, 2), (360, 1), (362, 1), (366, 1), (367, 1), (369, 2), (372, 1), (373, 1), (374, 1), (375, 1), (376, 2), (378, 1), (379, 2), (381, 1), (382, 1), (385, 1), (388, 1), (398, 2), (400, 2), (409, 1), (412, 1), (415, 1), (418, 7), (419, 5), (420, 4), (422, 1), (423, 2), (433, 1), (436, 5), (442, 1), (444, 2), (449, 1), (456, 1), (457, 17), (464, 4), (478, 1), (482, 1), (495, 1), (502, 1), (513, 1), (521, 1), (522, 1), (524, 1), (526, 1), (527, 1), (528, 2), (531, 1), (532, 1), (533, 1), (536, 1), (543, 5), (544, 4), (545, 1), (549, 2), (550, 1), (558, 3), (560, 6), (583, 3), (590, 1), (591, 1), (593, 1), (594, 3), (598, 1), (600, 1), (611, 1), (613, 1), (614, 3), (619, 1), (629, 1), (632, 1), (633, 1), (634, 1), (636, 1), (638, 1), (643, 4), (644, 2), (645, 1), (650, 2), (654, 1), (656, 1), (673, 1), (677, 1), (681, 1), (682, 1), (685, 1), (694, 1), (695, 3), (708, 1), (716, 1), (718, 1), (720, 1), (729, 1), (736, 3), (737, 2), (738, 1), (741, 4), (744, 3), (750, 5), (751, 1), (761, 1), (763, 1), (770, 1), (774, 3), (775, 1), (781, 1), (787, 1), (789, 1), (794, 1), (813, 1), (826, 1), (844, 1), (845, 2), (847, 1), (859, 3), (869, 1), (874, 1), (887, 1), (901, 2), (904, 1), (911, 3), (922, 1), (934, 2), (943, 1), (953, 1), (956, 1), (959, 1), (960, 1), (963, 2), (965, 3), (969, 1), (971, 1), (973, 1), (976, 1), (983, 1), (991, 1), (993, 1), (994, 1), (995, 1), (1005, 1), (1006, 1), (1017, 2), (1024, 1), (1037, 3), (1038, 1), (1041, 1), (1044, 1), (1046, 2), (1050, 1), (1053, 3), (1068, 1), (1075, 2), (1090, 1), (1092, 3), (1098, 1), (1110, 1), (1111, 2), (1115, 1), (1116, 1), (1117, 2), (1137, 1), (1142, 1), (1143, 1), (1146, 2), (1147, 1), (1150, 1), (1151, 1), (1166, 1), (1171, 1), (1180, 1), (1182, 1), (1186, 1), (1191, 1), (1198, 1), (1202, 1), (1204, 1), (1213, 1), (1215, 1), (1219, 1), (1222, 8), (1226, 2), (1227, 2), (1230, 1), (1235, 1), (1237, 4), (1251, 1), (1254, 2), (1257, 2), (1258, 2), (1262, 6), (1263, 4), (1264, 1), (1270, 1), (1271, 1), (1272, 1), (1274, 1), (1275, 1), (1278, 1), (1288, 1), (1289, 2), (1299, 1), (1301, 1), (1306, 1), (1309, 1), (1314, 1), (1326, 2), (1343, 4), (1350, 1), (1354, 6), (1355, 3), (1358, 1), (1360, 3), (1361, 1), (1371, 1), (1373, 1), (1374, 1), (1393, 1), (1399, 3), (1406, 1), (1421, 1), (1432, 1), (1445, 1), (1456, 1), (1466, 1), (1475, 1), (1480, 1), (1497, 1), (1505, 1), (1510, 1), (1511, 3), (1516, 1), (1521, 1), (1526, 1), (1530, 1), (1542, 1), (1544, 1), (1554, 1), (1558, 1), (1560, 1), (1565, 1), (1585, 1), (1586, 1), (1597, 2), (1603, 1), (1605, 2), (1631, 1), (1637, 1), (1640, 1), (1646, 1), (1647, 1), (1655, 1), (1657, 8), (1660, 1), (1668, 2), (1670, 1), (1685, 1), (1707, 1), (1714, 1), (1719, 1), (1720, 1), (1722, 1), (1748, 1), (1751, 2), (1755, 1), (1760, 1), (1774, 1), (1782, 1), (1793, 1), (1797, 2), (1798, 1), (1801, 1), (1802, 2), (1806, 2), (1817, 1), (1818, 1), (1824, 2), (1826, 1), (1830, 1), (1832, 1), (1839, 1), (1844, 1), (1852, 1), (1882, 1), (1908, 4), (1922, 2), (1937, 2), (1940, 5), (1949, 6), (1950, 1), (1951, 1), (1957, 3), (1961, 1), (1969, 1), (1975, 2), (1990, 1), (1991, 1), (2026, 2), (2027, 1), (2034, 1), (2035, 1), (2043, 1), (2046, 1), (2048, 1), (2049, 2), (2055, 1), (2059, 1), (2069, 3), (2071, 1), (2074, 1), (2077, 2), (2089, 1), (2094, 1), (2101, 1), (2129, 1), (2137, 1), (2148, 2), (2154, 3), (2157, 1), (2160, 1), (2192, 1), (2203, 1), (2204, 1), (2205, 1), (2225, 1), (2240, 1), (2253, 2), (2258, 1), (2262, 1), (2276, 1), (2290, 1), (2293, 1), (2294, 1), (2301, 1), (2306, 1), (2312, 2), (2335, 1), (2351, 1), (2362, 1), (2429, 1), (2442, 1), (2449, 1), (2453, 2), (2463, 1), (2467, 2), (2479, 1), (2481, 1), (2485, 1), (2508, 1), (2515, 4), (2517, 1), (2518, 1), (2534, 3), (2542, 1), (2561, 1), (2571, 1), (2575, 1), (2576, 1), (2597, 1), (2605, 1), (2616, 4), (2656, 1), (2677, 1), (2690, 1), (2698, 1), (2726, 2), (2727, 2), (2737, 2), (2738, 1), (2781, 1), (2785, 1), (2797, 1), (2798, 1), (2814, 1), (2830, 2), (2835, 1), (2852, 1), (2855, 5), (2864, 1), (2928, 2), (2931, 2), (2935, 1), (2937, 1), (2939, 8), (2949, 2), (2969, 1), (3020, 1), (3026, 1), (3027, 12), (3036, 1), (3037, 1), (3038, 1), (3039, 1), (3040, 1), (3041, 1), (3042, 1), (3043, 2), (3044, 1), (3045, 1), (3046, 1), (3047, 4), (3048, 1), (3049, 1), (3050, 1), (3051, 1), (3052, 1), (3053, 1), (3054, 1), (3055, 1), (3056, 2), (3057, 1), (3058, 1), (3059, 1), (3060, 1), (3061, 1), (3062, 1), (3063, 2), (3064, 1), (3065, 2), (3066, 1), (3067, 1), (3068, 1), (3069, 1), (3070, 1), (3071, 1), (3072, 1), (3073, 1), (3074, 1), (3075, 1), (3076, 1), (3077, 1), (3078, 1), (3079, 1), (3080, 1), (3081, 3), (3082, 1), (3083, 1), (3084, 1), (3085, 1), (3086, 1), (3087, 1), (3088, 1), (3089, 1), (3090, 1), (3091, 1), (3092, 1), (3093, 1), (3094, 1), (3095, 1), (3096, 1), (3097, 1), (3098, 1), (3099, 1), (3100, 2), (3101, 1), (3102, 1), (3103, 1), (3104, 1), (3105, 1), (3106, 1), (3107, 1), (3108, 1), (3109, 1), (3110, 3), (3111, 1), (3112, 1), (3113, 1), (3114, 1), (3115, 1), (3116, 1), (3117, 1), (3118, 1), (3119, 1), (3120, 1), (3121, 1), (3122, 1), (3123, 1), (3124, 1), (3125, 1), (3126, 1), (3127, 1), (3128, 1), (3129, 1), (3130, 2), (3131, 1), (3132, 1), (3133, 1), (3134, 1), (3135, 1), (3136, 1), (3137, 1), (3138, 1), (3139, 1), (3140, 1), (3141, 2), (3142, 1), (3143, 1), (3144, 1), (3145, 6), (3146, 1), (3147, 1), (3148, 1), (3149, 1), (3150, 1), (3151, 1), (3152, 1), (3153, 1), (3154, 1), (3155, 1), (3156, 1), (3157, 1), (3158, 1), (3159, 1), (3160, 1), (3161, 1), (3162, 3), (3163, 1), (3164, 1), (3165, 1), (3166, 1), (3167, 1), (3168, 1), (3169, 1), (3170, 1), (3171, 1), (3172, 1), (3173, 1), (3174, 1), (3175, 1), (3176, 1), (3177, 1), (3178, 2), (3179, 1), (3180, 1), (3181, 1), (3182, 1), (3183, 1), (3184, 1), (3185, 1), (3186, 1), (3187, 1), (3188, 3), (3189, 1), (3190, 1), (3191, 1), (3192, 1), (3193, 1), (3194, 1), (3195, 1), (3196, 1), (3197, 1), (3198, 1), (3199, 1), (3200, 1), (3201, 1), (3202, 1), (3203, 1), (3204, 1), (3205, 1), (3206, 1), (3207, 1), (3208, 1), (3209, 1), (3210, 1), (3211, 1), (3212, 1), (3213, 1), (3214, 1), (3215, 1), (3216, 1), (3217, 2), (3218, 1), (3219, 1), (3220, 1), (3221, 1), (3222, 1), (3223, 1), (3224, 1), (3225, 1), (3226, 1), (3227, 1), (3228, 1), (3229, 1), (3230, 1), (3231, 1), (3232, 2), (3233, 1), (3234, 1), (3235, 1), (3236, 1), (3237, 1), (3238, 2), (3239, 1), (3240, 2), (3241, 1), (3242, 1), (3243, 1), (3244, 1), (3245, 1), (3246, 1), (3247, 1), (3248, 1), (3249, 3), (3250, 1), (3251, 1), (3252, 1), (3253, 1), (3254, 2), (3255, 1), (3256, 1), (3257, 1), (3258, 1), (3259, 1), (3260, 1), (3261, 1), (3262, 1), (3263, 1), (3264, 2), (3265, 1), (3266, 1), (3267, 1), (3268, 2), (3269, 3), (3270, 1), (3271, 1), (3272, 1), (3273, 1), (3274, 1), (3275, 1), (3276, 1), (3277, 1), (3278, 4), (3279, 1), (3280, 1), (3281, 2), (3282, 1), (3283, 1), (3284, 1), (3285, 1), (3286, 1), (3287, 1), (3288, 1), (3289, 1), (3290, 1), (3291, 1), (3292, 1), (3293, 1), (3294, 1), (3295, 1), (3296, 1), (3297, 1), (3298, 1), (3299, 1), (3300, 1), (3301, 1), (3302, 1), (3303, 1), (3304, 1), (3305, 1), (3306, 1), (3307, 1), (3308, 1), (3309, 1), (3310, 1), (3311, 1), (3312, 1), (3313, 2), (3314, 1), (3315, 1), (3316, 1), (3317, 1), (3318, 1), (3319, 1), (3320, 1), (3321, 1), (3322, 1), (3323, 1), (3324, 3), (3325, 1), (3326, 1), (3327, 1), (3328, 1), (3329, 1), (3330, 1), (3331, 1), (3332, 1), (3333, 1), (3334, 1), (3335, 1), (3336, 1), (3337, 2), (3338, 1), (3339, 1), (3340, 1), (3341, 1), (3342, 2), (3343, 1), (3344, 1), (3345, 1), (3346, 1), (3347, 1), (3348, 1), (3349, 1), (3350, 1), (3351, 1), (3352, 1), (3353, 1), (3354, 1), (3355, 1), (3356, 1), (3357, 1), (3358, 1), (3359, 1), (3360, 1), (3361, 1), (3362, 1), (3363, 1), (3364, 1), (3365, 1), (3366, 1), (3367, 1), (3368, 1), (3369, 1), (3370, 1), (3371, 1), (3372, 1), (3373, 1), (3374, 1), (3375, 1), (3376, 1), (3377, 2), (3378, 1), (3379, 1), (3380, 1), (3381, 1), (3382, 1), (3383, 1), (3384, 1), (3385, 1), (3386, 3), (3387, 1), (3388, 1), (3389, 1), (3390, 5), (3391, 1), (3392, 1), (3393, 1), (3394, 1), (3395, 1), (3396, 1), (3397, 2), (3398, 1), (3399, 1), (3400, 1), (3401, 1), (3402, 1), (3403, 1), (3404, 1), (3405, 1), (3406, 1), (3407, 1), (3408, 1), (3409, 1), (3410, 1), (3411, 1), (3412, 1), (3413, 1), (3414, 1), (3415, 1), (3416, 1), (3417, 1), (3418, 1), (3419, 1), (3420, 1), (3421, 1), (3422, 1), (3423, 1), (3424, 1), (3425, 1), (3426, 1), (3427, 1), (3428, 3), (3429, 1), (3430, 1), (3431, 1), (3432, 1), (3433, 1), (3434, 2), (3435, 1), (3436, 3), (3437, 1), (3438, 1), (3439, 3), (3440, 1), (3441, 1), (3442, 1), (3443, 1), (3444, 2), (3445, 1), (3446, 1), (3447, 1), (3448, 1), (3449, 1), (3450, 1), (3451, 1), (3452, 1), (3453, 1), (3454, 1), (3455, 1), (3456, 1), (3457, 1), (3458, 1), (3459, 1), (3460, 1), (3461, 1), (3462, 6), (3463, 1), (3464, 1), (3465, 2), (3466, 1), (3467, 1), (3468, 1), (3469, 1), (3470, 1), (3471, 1), (3472, 2), (3473, 1), (3474, 1), (3475, 2), (3476, 1), (3477, 1), (3478, 1), (3479, 1)], [(0, 1), (6, 1), (7, 1), (12, 2), (24, 1), (25, 1), (26, 2), (30, 4), (37, 1), (39, 1), (40, 1), (44, 1), (49, 1), (51, 3), (56, 2), (62, 1), (68, 5), (69, 1), (74, 2), (77, 1), (80, 1), (83, 1), (85, 3), (93, 1), (97, 1), (98, 2), (99, 1), (107, 1), (111, 2), (117, 3), (132, 2), (133, 1), (137, 1), (138, 1), (140, 3), (142, 1), (144, 3), (150, 2), (157, 1), (162, 3), (164, 1), (168, 16), (170, 1), (174, 2), (176, 3), (179, 1), (190, 1), (191, 2), (200, 1), (213, 2), (215, 1), (217, 1), (224, 1), (227, 2), (229, 2), (234, 1), (249, 3), (251, 8), (256, 5), (259, 1), (261, 5), (268, 2), (269, 1), (270, 3), (271, 6), (273, 4), (275, 3), (282, 3), (283, 4), (287, 1), (288, 1), (289, 2), (293, 3), (297, 6), (303, 2), (310, 1), (313, 1), (321, 11), (331, 1), (337, 2), (346, 1), (354, 2), (355, 1), (356, 2), (359, 1), (362, 3), (372, 1), (376, 1), (394, 5), (397, 6), (409, 2), (412, 1), (415, 1), (418, 1), (419, 2), (420, 6), (444, 1), (445, 1), (470, 1), (471, 3), (482, 1), (492, 1), (495, 1), (506, 1), (518, 1), (527, 1), (537, 1), (543, 1), (549, 1), (560, 1), (579, 2), (581, 1), (584, 3), (589, 1), (590, 1), (591, 2), (593, 1), (619, 1), (620, 1), (629, 1), (633, 1), (642, 4), (643, 1), (645, 2), (650, 1), (656, 1), (659, 1), (672, 3), (690, 2), (692, 1), (695, 2), (697, 3), (720, 2), (722, 2), (736, 5), (749, 1), (758, 3), (773, 4), (774, 3), (780, 2), (789, 1), (790, 1), (794, 1), (800, 1), (809, 4), (810, 1), (815, 1), (823, 1), (828, 1), (835, 2), (837, 1), (851, 1), (873, 1), (886, 1), (897, 1), (901, 1), (910, 1), (915, 1), (923, 1), (924, 2), (932, 3), (944, 1), (945, 2), (946, 1), (949, 1), (950, 1), (953, 3), (963, 2), (971, 1), (972, 8), (973, 6), (978, 2), (983, 2), (988, 2), (1001, 2), (1003, 1), (1011, 24), (1015, 1), (1017, 1), (1022, 1), (1024, 1), (1030, 4), (1031, 1), (1046, 1), (1049, 3), (1053, 2), (1072, 1), (1090, 2), (1092, 4), (1112, 1), (1118, 1), (1135, 1), (1142, 2), (1144, 1), (1146, 1), (1156, 1), (1158, 1), (1176, 1), (1183, 1), (1204, 1), (1216, 1), (1217, 3), (1219, 1), (1222, 1), (1224, 1), (1226, 1), (1235, 2), (1237, 2), (1241, 5), (1245, 2), (1247, 1), (1255, 1), (1258, 1), (1267, 5), (1272, 1), (1293, 3), (1300, 1), (1310, 1), (1325, 1), (1326, 2), (1352, 2), (1361, 1), (1372, 1), (1375, 1), (1377, 1), (1426, 2), (1430, 2), (1432, 2), (1435, 4), (1438, 2), (1440, 4), (1441, 1), (1445, 1), (1447, 1), (1448, 5), (1450, 2), (1457, 1), (1458, 1), (1461, 1), (1473, 1), (1488, 1), (1493, 1), (1503, 1), (1508, 1), (1511, 1), (1520, 1), (1528, 1), (1530, 1), (1546, 1), (1571, 3), (1586, 3), (1591, 1), (1594, 1), (1609, 1), (1615, 1), (1627, 1), (1629, 1), (1631, 2), (1633, 1), (1647, 1), (1655, 1), (1670, 1), (1679, 5), (1697, 1), (1702, 1), (1703, 2), (1710, 1), (1715, 3), (1718, 1), (1720, 1), (1729, 1), (1732, 1), (1738, 1), (1753, 1), (1768, 4), (1804, 6), (1806, 2), (1807, 1), (1827, 2), (1832, 1), (1862, 2), (1881, 1), (1924, 3), (1966, 3), (1969, 1), (1975, 4), (1976, 3), (1983, 2), (1990, 1), (2009, 1), (2033, 1), (2064, 1), (2077, 2), (2099, 1), (2101, 1), (2105, 1), (2120, 1), (2132, 1), (2153, 1), (2188, 3), (2197, 1), (2210, 1), (2218, 1), (2288, 1), (2301, 1), (2306, 1), (2310, 2), (2414, 1), (2457, 1), (2466, 1), (2479, 2), (2517, 1), (2518, 1), (2545, 1), (2561, 1), (2600, 1), (2607, 3), (2651, 1), (2659, 1), (2660, 1), (2698, 23), (2701, 1), (2716, 1), (2725, 1), (2726, 1), (2735, 3), (2738, 3), (2751, 1), (2785, 1), (2855, 3), (2869, 1), (2875, 4), (2889, 1), (2893, 1), (2914, 1), (2931, 2), (2979, 2), (3017, 2), (3020, 1), (3080, 1), (3097, 1), (3100, 1), (3139, 1), (3146, 1), (3270, 1), (3284, 1), (3403, 1), (3410, 1), (3447, 1), (3480, 1), (3481, 1), (3482, 3), (3483, 1), (3484, 1), (3485, 1), (3486, 2), (3487, 1), (3488, 1), (3489, 2), (3490, 1), (3491, 1), (3492, 1), (3493, 5), (3494, 2), (3495, 1), (3496, 1), (3497, 2), (3498, 1), (3499, 2), (3500, 1), (3501, 3), (3502, 1), (3503, 1), (3504, 1), (3505, 1), (3506, 1), (3507, 1), (3508, 1), (3509, 1), (3510, 1), (3511, 1), (3512, 1), (3513, 1), (3514, 1), (3515, 1), (3516, 2), (3517, 1), (3518, 1), (3519, 1), (3520, 1), (3521, 2), (3522, 1), (3523, 1), (3524, 2), (3525, 1), (3526, 1), (3527, 1), (3528, 1), (3529, 1), (3530, 3), (3531, 1), (3532, 2), (3533, 3), (3534, 6), (3535, 9), (3536, 1), (3537, 1), (3538, 1), (3539, 1), (3540, 5), (3541, 1), (3542, 1), (3543, 1), (3544, 1), (3545, 4), (3546, 3), (3547, 1), (3548, 2), (3549, 1), (3550, 1), (3551, 2), (3552, 1), (3553, 1), (3554, 2), (3555, 1), (3556, 1), (3557, 1), (3558, 6), (3559, 1), (3560, 1), (3561, 2), (3562, 1), (3563, 1), (3564, 2), (3565, 1), (3566, 1), (3567, 2), (3568, 2), (3569, 3), (3570, 1), (3571, 1), (3572, 1), (3573, 1), (3574, 1), (3575, 1), (3576, 1), (3577, 1), (3578, 2), (3579, 3), (3580, 1), (3581, 1), (3582, 1), (3583, 1), (3584, 1), (3585, 1), (3586, 2), (3587, 1), (3588, 1), (3589, 1), (3590, 1), (3591, 1), (3592, 2), (3593, 1), (3594, 1), (3595, 1), (3596, 5), (3597, 1), (3598, 1), (3599, 4), (3600, 2), (3601, 2), (3602, 1), (3603, 1), (3604, 2), (3605, 2), (3606, 1), (3607, 1), (3608, 1), (3609, 1), (3610, 1), (3611, 1), (3612, 1), (3613, 1), (3614, 1), (3615, 1), (3616, 1), (3617, 1), (3618, 1), (3619, 1), (3620, 5), (3621, 1), (3622, 1), (3623, 1), (3624, 1), (3625, 1), (3626, 1), (3627, 5), (3628, 1), (3629, 1), (3630, 1), (3631, 1), (3632, 2), (3633, 1), (3634, 1), (3635, 2), (3636, 1), (3637, 1), (3638, 1), (3639, 1), (3640, 1), (3641, 1), (3642, 1), (3643, 1), (3644, 2), (3645, 1), (3646, 1), (3647, 1), (3648, 1), (3649, 1), (3650, 1), (3651, 1), (3652, 6), (3653, 5), (3654, 1), (3655, 1), (3656, 1), (3657, 1), (3658, 1)], [(17, 1), (25, 1), (35, 1), (44, 1), (45, 1), (55, 1), (62, 1), (68, 4), (80, 1), (85, 1), (89, 1), (91, 1), (97, 2), (99, 1), (140, 1), (144, 5), (147, 1), (150, 1), (164, 1), (168, 1), (170, 1), (175, 2), (176, 1), (191, 1), (194, 1), (212, 3), (220, 3), (222, 1), (227, 1), (231, 1), (234, 3), (236, 1), (251, 8), (256, 1), (261, 1), (262, 1), (270, 2), (276, 1), (279, 1), (287, 1), (288, 1), (300, 2), (305, 1), (311, 1), (313, 1), (321, 14), (327, 1), (329, 1), (337, 1), (338, 1), (354, 4), (358, 1), (376, 1), (387, 2), (391, 2), (401, 1), (406, 2), (418, 1), (419, 2), (420, 2), (433, 1), (442, 1), (445, 1), (480, 1), (495, 4), (502, 1), (518, 1), (538, 1), (544, 1), (545, 1), (549, 1), (550, 1), (584, 1), (591, 1), (604, 2), (606, 1), (611, 1), (618, 1), (621, 1), (629, 1), (659, 1), (667, 1), (672, 1), (682, 1), (684, 2), (706, 1), (720, 1), (722, 1), (732, 1), (736, 1), (738, 5), (751, 2), (755, 1), (770, 1), (773, 3), (786, 1), (803, 1), (826, 1), (827, 5), (845, 1), (846, 2), (859, 1), (896, 1), (904, 1), (923, 1), (935, 1), (947, 1), (949, 2), (960, 1), (963, 3), (976, 2), (978, 1), (1016, 2), (1030, 1), (1031, 2), (1034, 1), (1090, 2), (1213, 1), (1227, 2), (1255, 1), (1262, 1), (1264, 1), (1268, 2), (1272, 2), (1278, 4), (1290, 1), (1311, 1), (1338, 1), (1355, 1), (1409, 1), (1422, 1), (1423, 1), (1424, 1), (1432, 1), (1435, 1), (1450, 1), (1453, 1), (1463, 1), (1473, 1), (1479, 1), (1480, 1), (1497, 2), (1515, 1), (1533, 2), (1539, 1), (1551, 9), (1552, 7), (1553, 1), (1567, 1), (1571, 1), (1586, 2), (1596, 1), (1599, 1), (1604, 1), (1618, 1), (1627, 1), (1631, 1), (1677, 1), (1683, 1), (1694, 1), (1710, 1), (1715, 1), (1729, 1), (1732, 2), (1734, 2), (1735, 1), (1738, 1), (1752, 1), (1753, 1), (1756, 1), (1775, 1), (1777, 2), (1780, 1), (1788, 1), (1826, 1), (1878, 1), (1884, 1), (1897, 1), (1914, 1), (1976, 2), (1990, 1), (2020, 1), (2055, 1), (2094, 1), (2099, 1), (2105, 2), (2107, 1), (2122, 1), (2169, 1), (2188, 1), (2197, 1), (2212, 2), (2214, 1), (2276, 1), (2336, 1), (2353, 1), (2468, 2), (2546, 1), (2551, 1), (2562, 1), (2581, 1), (2586, 1), (2659, 1), (2670, 3), (2677, 11), (2704, 1), (2746, 1), (2761, 1), (2769, 1), (2788, 1), (2821, 1), (2837, 1), (2852, 1), (2931, 1), (2973, 1), (2978, 1), (3062, 1), (3073, 1), (3079, 1), (3188, 1), (3200, 1), (3410, 1), (3436, 1), (3494, 1), (3525, 1), (3530, 1), (3557, 1), (3579, 3), (3585, 1), (3602, 2), (3612, 5), (3659, 1), (3660, 1), (3661, 1), (3662, 1), (3663, 1), (3664, 1), (3665, 2), (3666, 1), (3667, 1), (3668, 1), (3669, 3), (3670, 1), (3671, 1), (3672, 1), (3673, 1), (3674, 1), (3675, 1), (3676, 1), (3677, 2), (3678, 1), (3679, 1), (3680, 1), (3681, 1), (3682, 1), (3683, 1), (3684, 1), (3685, 1), (3686, 1), (3687, 13), (3688, 1), (3689, 1), (3690, 2), (3691, 1), (3692, 5), (3693, 1), (3694, 1), (3695, 1), (3696, 2), (3697, 2), (3698, 1), (3699, 1), (3700, 1), (3701, 15), (3702, 9), (3703, 2), (3704, 1), (3705, 2), (3706, 1), (3707, 1), (3708, 1), (3709, 1), (3710, 1), (3711, 1), (3712, 1), (3713, 2), (3714, 2), (3715, 8), (3716, 2), (3717, 1), (3718, 1), (3719, 1), (3720, 1), (3721, 1), (3722, 1), (3723, 1), (3724, 2), (3725, 1), (3726, 1), (3727, 1), (3728, 1), (3729, 1), (3730, 2), (3731, 1), (3732, 1), (3733, 1), (3734, 1), (3735, 2), (3736, 1), (3737, 5), (3738, 1), (3739, 1), (3740, 1), (3741, 1), (3742, 1), (3743, 1), (3744, 1), (3745, 1), (3746, 1), (3747, 1), (3748, 1), (3749, 1), (3750, 1), (3751, 1), (3752, 1), (3753, 1), (3754, 1), (3755, 1), (3756, 1), (3757, 1)], [(12, 2), (25, 4), (29, 1), (30, 2), (32, 1), (37, 1), (46, 1), (49, 4), (68, 5), (85, 1), (86, 2), (93, 2), (98, 6), (107, 3), (112, 1), (132, 1), (133, 2), (138, 1), (140, 1), (144, 2), (150, 1), (151, 1), (156, 2), (157, 2), (164, 1), (168, 6), (170, 8), (174, 1), (175, 1), (186, 1), (188, 1), (191, 2), (196, 1), (205, 1), (215, 1), (217, 1), (218, 1), (222, 1), (227, 2), (232, 1), (240, 1), (248, 1), (249, 3), (251, 37), (256, 2), (261, 1), (262, 4), (263, 2), (268, 2), (270, 2), (271, 4), (273, 2), (279, 1), (282, 3), (283, 1), (287, 2), (289, 1), (290, 1), (309, 1), (319, 1), (321, 16), (331, 2), (337, 3), (354, 4), (355, 1), (373, 2), (374, 1), (376, 1), (379, 2), (386, 3), (388, 2), (389, 2), (394, 2), (409, 2), (411, 4), (419, 5), (420, 5), (424, 1), (427, 1), (437, 8), (446, 1), (449, 1), (456, 1), (469, 3), (471, 1), (478, 1), (492, 1), (502, 2), (503, 2), (522, 1), (537, 2), (545, 1), (550, 1), (551, 1), (552, 1), (558, 1), (560, 1), (562, 3), (567, 2), (569, 3), (573, 2), (583, 1), (584, 1), (585, 2), (586, 2), (587, 1), (590, 1), (593, 1), (608, 1), (610, 5), (614, 3), (616, 2), (620, 1), (622, 3), (624, 2), (629, 2), (632, 1), (636, 1), (637, 1), (643, 2), (645, 9), (649, 1), (650, 3), (667, 4), (672, 9), (684, 1), (693, 2), (694, 1), (695, 1), (697, 1), (701, 1), (708, 2), (720, 2), (722, 1), (738, 1), (744, 1), (745, 1), (748, 1), (750, 1), (765, 1), (774, 1), (778, 1), (780, 1), (785, 2), (804, 1), (813, 1), (822, 1), (827, 1), (828, 1), (844, 1), (859, 2), (874, 1), (875, 1), (879, 1), (881, 3), (887, 2), (900, 1), (905, 1), (907, 1), (921, 3), (922, 1), (924, 1), (932, 1), (935, 10), (947, 1), (950, 2), (957, 1), (965, 4), (969, 2), (983, 3), (988, 2), (1005, 1), (1008, 1), (1017, 1), (1027, 1), (1030, 1), (1040, 1), (1049, 4), (1050, 1), (1071, 1), (1072, 1), (1075, 1), (1080, 1), (1092, 1), (1110, 2), (1130, 1), (1134, 1), (1150, 1), (1169, 1), (1180, 1), (1219, 2), (1227, 1), (1255, 1), (1264, 3), (1267, 1), (1271, 2), (1272, 1), (1291, 1), (1294, 1), (1295, 1), (1311, 2), (1320, 3), (1347, 1), (1352, 1), (1355, 2), (1360, 1), (1361, 1), (1375, 1), (1410, 1), (1416, 1), (1423, 1), (1426, 1), (1451, 2), (1468, 1), (1473, 2), (1480, 1), (1490, 2), (1505, 1), (1523, 1), (1548, 1), (1567, 1), (1571, 3), (1577, 1), (1588, 1), (1598, 1), (1599, 1), (1609, 1), (1610, 1), (1611, 1), (1619, 2), (1646, 1), (1647, 1), (1658, 2), (1669, 1), (1670, 1), (1672, 1), (1677, 1), (1681, 2), (1687, 1), (1691, 2), (1693, 1), (1696, 1), (1697, 1), (1706, 1), (1716, 1), (1720, 2), (1733, 1), (1802, 2), (1806, 1), (1827, 1), (1846, 1), (1847, 1), (1853, 2), (1892, 1), (1940, 1), (1951, 1), (1969, 1), (1976, 1), (1990, 5), (2065, 1), (2074, 1), (2101, 1), (2105, 1), (2106, 2), (2122, 1), (2134, 1), (2149, 1), (2169, 3), (2180, 1), (2222, 2), (2240, 2), (2275, 1), (2276, 2), (2279, 2), (2320, 1), (2325, 1), (2336, 1), (2402, 1), (2581, 7), (2600, 3), (2603, 1), (2627, 1), (2652, 1), (2675, 1), (2700, 1), (2704, 1), (2713, 2), (2751, 1), (2769, 1), (2770, 1), (2780, 4), (2781, 4), (2789, 1), (2824, 6), (2828, 1), (2847, 3), (2863, 1), (2864, 1), (2869, 1), (2894, 1), (2910, 1), (2931, 2), (2935, 1), (2937, 1), (2957, 1), (2987, 1), (2997, 1), (3002, 1), (3003, 10), (3011, 1), (3100, 1), (3112, 1), (3113, 2), (3139, 1), (3144, 1), (3175, 1), (3386, 1), (3409, 1), (3424, 1), (3431, 1), (3454, 1), (3480, 1), (3536, 2), (3538, 1), (3542, 1), (3552, 1), (3562, 1), (3574, 1), (3612, 2), (3616, 1), (3663, 1), (3670, 1), (3680, 1), (3752, 1), (3758, 1), (3759, 1), (3760, 1), (3761, 1), (3762, 1), (3763, 1), (3764, 1), (3765, 2), (3766, 1), (3767, 1), (3768, 1), (3769, 1), (3770, 1), (3771, 1), (3772, 1), (3773, 2), (3774, 1), (3775, 1), (3776, 1), (3777, 2), (3778, 1), (3779, 1), (3780, 4), (3781, 6), (3782, 3), (3783, 1), (3784, 1), (3785, 1), (3786, 3), (3787, 1), (3788, 1), (3789, 1), (3790, 1), (3791, 1), (3792, 1), (3793, 1), (3794, 1), (3795, 1), (3796, 1), (3797, 1), (3798, 1), (3799, 3), (3800, 2), (3801, 1), (3802, 1), (3803, 1), (3804, 1), (3805, 1), (3806, 1), (3807, 1), (3808, 1), (3809, 1), (3810, 1), (3811, 1), (3812, 1), (3813, 6), (3814, 12), (3815, 1), (3816, 1), (3817, 1), (3818, 1), (3819, 1), (3820, 1), (3821, 1), (3822, 1), (3823, 2), (3824, 13), (3825, 2), (3826, 1), (3827, 3), (3828, 1), (3829, 1), (3830, 1), (3831, 1), (3832, 1), (3833, 1), (3834, 1), (3835, 1), (3836, 1), (3837, 1), (3838, 1), (3839, 2), (3840, 1), (3841, 1), (3842, 1), (3843, 2), (3844, 1), (3845, 1), (3846, 1), (3847, 1), (3848, 1), (3849, 1), (3850, 1), (3851, 1), (3852, 1), (3853, 1), (3854, 5), (3855, 1), (3856, 1), (3857, 1), (3858, 1), (3859, 1), (3860, 2), (3861, 1), (3862, 2), (3863, 1), (3864, 1), (3865, 1), (3866, 1), (3867, 1), (3868, 1), (3869, 1), (3870, 1), (3871, 1), (3872, 1), (3873, 1), (3874, 1), (3875, 1), (3876, 2), (3877, 1), (3878, 1), (3879, 1), (3880, 10), (3881, 3), (3882, 2), (3883, 1), (3884, 1), (3885, 1), (3886, 1), (3887, 1), (3888, 1), (3889, 1), (3890, 1), (3891, 1)]]\n"
     ]
    }
   ],
   "source": [
    "print(doc_term)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LDA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# specify number of topics\n",
    "num_topics = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create LDA model\n",
    "lda_model = gensim.models.LdaModel(corpus=doc_term,\n",
    "                                   id2word=dictionary,\n",
    "                                   num_topics=num_topics)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lda_model.print_topics(num_topics=num_topics, num_words=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}