題目描述

小根某日夢到自己進入了一個神秘的國度。那裏，大魔王準備了一個難題等他⋯⋯

大魔王共給小根 T 次挑戰。只有完成全部挑戰小根才能逃離夢魘。每次挑戰中，大魔王會給小根 n 盞可開關的燈和一個整數 m (1 <= m <= n)。一開始，這些燈被排列在一個圓圈上，且全部燈都是關上的。小根需要通過若干輪操作開啟所有燈。在每輪操作中，小根可以選 m 盞不同的燈並改變它們的狀態；也就是說，開的燈會在操作後變為關的，關的燈則會被開啟。

大魔王當然不想小根輕易逃脫，所以它準備的燈都十分脆弱。若果在達成任務前過多地開關這些燈，小根便可能損壞它們，任務就永遠不能成功。小心翼翼的他希望你幫忙求出至少需要多少輪才能闖關。

魔王十分奸詐！夢裏的小根突然意識到，對某些情況 (例如 n=3, m=2)，無論他如何操作，根本沒有方法可開啟所有燈。如果真的這樣，小根只需肯定地告訴大魔王他出了一道無解的假題。

輸入格式

第一行有一正整數 T (1 <= T <= 100)，表示接下來有 T 次獨立的挑戰 (測資)。

每個測資中共一行，給定兩個非負整數代表一對 n m。

0 <= m <= n = 1。保證所有測資的 n 之和不超過 3000。

輸出格式

對大魔王的每次挑戰輸出操作次數的最小值。若該情況不存在方法使所有燈同時亮起，只需輸出 "IMPOSSIBLE" (不需括號)。保證每個挑戰的答案是不大於 10⁹ 的整數或是 "IMPOSSIBLE"。

Samples

["4\r\n3 1\r\n6 3\r\n2 0\r\n7 7","5\r\n5 2\r\n5 3\r\n4 3\r\n7 6\r\n8 3"]

["3\r\n2\r\nIMPOSSIBLE\r\n1","IMPOSSIBLE\r\n3\r\n4\r\nIMPOSSIBLE\r\n4"]

提示

範例輸入#1中，第一個測資可做 3 次操作 (每次開啟一盞燈)；對第二個測資，我們可以先後操作 {1, 2, 3} 和 {4, 5, 6} 便能用 2 次開啟所有燈。這裏 i 號燈代表第 i 盞燈。

範例輸入#2中，第一次挑戰是不可行的，因為無論操作多少次，亮的燈的數目都是偶數；第二次挑戰可用 {1, 2, 3}, {2, 3, 5} 和 {2, 3, 4} 解決；而第三次挑戰可用 {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}。

系統能根據完成程度給予部分分數，子任務配分如下：

1. (10分) m = 0, 1
2. (20分) m = 0, 1, 2
3. (35分) T <= 5, n <= 16
4. (25分) 所有測資的 n 之和 <= 300
5. (10分) 無額外條件, i.e. n <= 3000

加油～

原始資料

• Zero1 題號：a801
• Hydro 題號：Z0801
• Locale：zh_TW
• Display：practice