/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<cctype>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 2000000000
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define LL long long
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
#define mm 10000000
string inttostring(int n)
{
stringstream a;
a<<n;
return a.str();
}
int stringtoint(string A)
{
istringstream a(A);
int p;
a>>p;
return p;
}
//////////////////////////////////////////////////////
class GeometricProgressions {
public:
int fac(LL num,set<int>& S)
{
for(LL c=2;c*c<=num;c++)
{
if(num%c==0)
{
S.insert(c);
while(num%c==0) num/=c;
}
}
if(num!=1) S.insert(num);
return 0;
}
int dec(LL num,vector<int>& V, vector<int> A)
{
f(i,0,A.size())
{
if(num%A[i]==0)
{
int c=0;
while(num%A[i]==0)
{
c++;
num/=A[i];
}
V.pb(c);
}
else V.pb(0);
}
return 0;
}
int count( int b1, int q1, int n1, int b2, int q2, int n2 ) {
if(b2==0 || q2<=1)
{
swap(b1,b2);
swap(q1,q2);
swap(n1,n2);
}
if(b1==0 || q1<=1)
{
set<LL> S;
S.insert(b1);
if(n1>1)
S.insert(b1*q1);
LL cur=b2;
f(i,0,n2)
{
S.insert(cur);
cur*=q2;
if(cur>500000000)
{
return (n2-i-1)+S.size();
}
}
return S.size();
}
set<int> factors;
fac(b1,factors);
fac(q1,factors);
fac(b2,factors);
fac(q2,factors);
vector<int> FF(all(factors));
set<vector<int> > SS;
vector<int> req1,req2,reb1,reb2;
dec(q1,req1,FF);
dec(q2,req2,FF);
dec(b1,reb1,FF);
dec(b2,reb2,FF);
f(i,0,n1)
{
SS.insert(reb1);
f(i,0,reb1.size())
{
reb1[i]+=req1[i];
}
}
f(i,0,n2)
{
SS.insert(reb2);
f(i,0,reb2.size())
{
reb2[i]+=req2[i];
}
}
return SS.size();
}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}
int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}
if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}
int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";
string verdict;
vector<string> info;
char buf[100];
if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}
if (expected == received) {
verdict = "PASSED";
} else {
verdict = "FAILED";
}
cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;
if (verdict == "FAILED") {
cerr << " Expected: " << expected << endl;
cerr << " Received: " << received << endl;
}
return verdict == "PASSED";
}
int run_test_case(int casenum__) {
switch (casenum__) {
case 0: {
int b1 = 3;
int q1 = 2;
int n1 = 5;
int b2 = 6;
int q2 = 2;
int n2 = 5;
int expected__ = 6;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 1: {
int b1 = 3;
int q1 = 2;
int n1 = 5;
int b2 = 2;
int q2 = 3;
int n2 = 5;
int expected__ = 9;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 2: {
int b1 = 1;
int q1 = 1;
int n1 = 1;
int b2 = 0;
int q2 = 0;
int n2 = 1;
int expected__ = 2;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 3: {
int b1 = 3;
int q1 = 4;
int n1 = 100500;
int b2 = 48;
int q2 = 1024;
int n2 = 1000;
int expected__ = 100500;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
// custom cases
/* case 4: {
int b1 = ;
int q1 = ;
int n1 = ;
int b2 = ;
int q2 = ;
int n2 = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
/* case 5: {
int b1 = ;
int q1 = ;
int n1 = ;
int b2 = ;
int q2 = ;
int n2 = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
/* case 6: {
int b1 = ;
int q1 = ;
int n1 = ;
int b2 = ;
int q2 = ;
int n2 = ;
int expected__ = ;
clock_t start__ = clock();
int received__ = GeometricProgressions().count(b1, q1, n1, b2, q2, n2);
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
default:
return -1;
}
}
}
int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE
LyoKd3JpdHRlbiBieS0gUGl5dXNoIEdvbGFuaQpsYW5ndWFnZS0gYysrCmNvdW50cnktIEluZGlhCkNvbGxlZ2UtIE4uSS5UIEphbXNoZWRwdXIKKi8KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxzc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPG1hcD4KI2luY2x1ZGU8c2V0PgojaW5jbHVkZTxxdWV1ZT4KI2luY2x1ZGU8Y2N0eXBlPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGFsbChzKSBzLmJlZ2luKCkscy5lbmQoKQojZGVmaW5lIGYoaSxhLGIpIGZvcihpbnQgaT1hO2k8YjtpKyspCiNkZWZpbmUgRihpLGEsYikgZm9yKGludCBpPWE7aT49YjtpLS0pCiNkZWZpbmUgUEkgMy4xNDE1OTI2NTM1ODk3OTMyMzg0NjI2NDMzODMyNzk1CiNkZWZpbmUgSU5GIDIwMDAwMDAwMDAKI2RlZmluZSBCSUdfSU5GIDcwMDAwMDAwMDAwMDAwMDAwMDBMTAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGVwcyAxZS05CiNkZWZpbmUgTEwgbG9uZyBsb25nCiNkZWZpbmUgc2kobikgc2NhbmYoIiVkIiwmbikKI2RlZmluZSBzbGwobikgc2NhbmYoIiVsbGQiLCZuKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgbW0gMTAwMDAwMDAKCnN0cmluZyBpbnR0b3N0cmluZyhpbnQgbikKewogICAgc3RyaW5nc3RyZWFtIGE7CiAgICBhPDxuOwogICAgcmV0dXJuIGEuc3RyKCk7Cn0KCmludCBzdHJpbmd0b2ludChzdHJpbmcgQSkKewogICAgaXN0cmluZ3N0cmVhbSBhKEEpOwogICAgaW50IHA7CiAgICBhPj5wOwogICAgcmV0dXJuIHA7Cn0KCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwoKY2xhc3MgR2VvbWV0cmljUHJvZ3Jlc3Npb25zIHsKcHVibGljOgogICAgaW50IGZhYyhMTCBudW0sc2V0PGludD4mIFMpCiAgICB7CiAgICAgICAgZm9yKExMIGM9MjtjKmM8PW51bTtjKyspCiAgICAgICAgewogICAgICAgICAgICBpZihudW0lYz09MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgUy5pbnNlcnQoYyk7CiAgICAgICAgICAgICAgICB3aGlsZShudW0lYz09MCkgbnVtLz1jOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmKG51bSE9MSkgUy5pbnNlcnQobnVtKTsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIGludCBkZWMoTEwgbnVtLHZlY3RvcjxpbnQ+JiBWLCB2ZWN0b3I8aW50PiBBKQogICAgewogICAgICAgIGYoaSwwLEEuc2l6ZSgpKQogICAgICAgIHsKICAgICAgICAgICAgaWYobnVtJUFbaV09PTApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBjPTA7CiAgICAgICAgICAgICAgICB3aGlsZShudW0lQVtpXT09MCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBjKys7CiAgICAgICAgICAgICAgICAgICAgbnVtLz1BW2ldOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgVi5wYihjKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIFYucGIoMCk7CiAgICAgICAgfQogICAgICAgIHJldHVybiAwOwogICAgfQogICBpbnQgY291bnQoIGludCBiMSwgaW50IHExLCBpbnQgbjEsIGludCBiMiwgaW50IHEyLCBpbnQgbjIgKSB7CiAgICBpZihiMj09MCB8fCBxMjw9MSkKICAgIHsKICAgICAgICBzd2FwKGIxLGIyKTsKICAgICAgICBzd2FwKHExLHEyKTsKICAgICAgICBzd2FwKG4xLG4yKTsKICAgIH0KICAgIGlmKGIxPT0wIHx8IHExPD0xKQogICAgewogICAgICAgIHNldDxMTD4gUzsKICAgICAgICBTLmluc2VydChiMSk7CiAgICAgICAgaWYobjE+MSkKICAgICAgICBTLmluc2VydChiMSpxMSk7CiAgICAgICAgTEwgY3VyPWIyOwogICAgICAgIGYoaSwwLG4yKQogICAgICAgIHsKICAgICAgICAgICAgUy5pbnNlcnQoY3VyKTsKICAgICAgICAgICAgY3VyKj1xMjsKICAgICAgICAgICAgaWYoY3VyPjUwMDAwMDAwMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmV0dXJuIChuMi1pLTEpK1Muc2l6ZSgpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBTLnNpemUoKTsKICAgIH0KCiAgICBzZXQ8aW50PiBmYWN0b3JzOwogICAgZmFjKGIxLGZhY3RvcnMpOwogICAgZmFjKHExLGZhY3RvcnMpOwogICAgZmFjKGIyLGZhY3RvcnMpOwogICAgZmFjKHEyLGZhY3RvcnMpOwogICAgdmVjdG9yPGludD4gRkYoYWxsKGZhY3RvcnMpKTsKCiAgICBzZXQ8dmVjdG9yPGludD4gPiBTUzsKCiAgICB2ZWN0b3I8aW50PiByZXExLHJlcTIscmViMSxyZWIyOwoKICAgIGRlYyhxMSxyZXExLEZGKTsKICAgIGRlYyhxMixyZXEyLEZGKTsKICAgIGRlYyhiMSxyZWIxLEZGKTsKICAgIGRlYyhiMixyZWIyLEZGKTsKCiAgICBmKGksMCxuMSkKICAgIHsKICAgICAgICBTUy5pbnNlcnQocmViMSk7CiAgICAgICAgZihpLDAscmViMS5zaXplKCkpCiAgICAgICAgewogICAgICAgICAgICByZWIxW2ldKz1yZXExW2ldOwogICAgICAgIH0KICAgIH0KCiAgICBmKGksMCxuMikKICAgIHsKICAgICAgICBTUy5pbnNlcnQocmViMik7CiAgICAgICAgZihpLDAscmViMi5zaXplKCkpCiAgICAgICAgewogICAgICAgICAgICByZWIyW2ldKz1yZXEyW2ldOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gU1Muc2l6ZSgpOwoKCiAgIH0KfTsKCi8vIEJFR0lOIENVVCBIRVJFCm5hbWVzcGFjZSBtb2pfaGFybmVzcyB7CiAgICBpbnQgcnVuX3Rlc3RfY2FzZShpbnQpOwoJdm9pZCBydW5fdGVzdChpbnQgY2FzZW51bSA9IC0xLCBib29sIHF1aWV0ID0gZmFsc2UpIHsKCQlpZiAoY2FzZW51bSAhPSAtMSkgewoJCQlpZiAocnVuX3Rlc3RfY2FzZShjYXNlbnVtKSA9PSAtMSAmJiAhcXVpZXQpIHsKCQkJCWNlcnIgPDwgIklsbGVnYWwgaW5wdXQhIFRlc3QgY2FzZSAiIDw8IGNhc2VudW0gPDwgIiBkb2VzIG5vdCBleGlzdC4iIDw8IGVuZGw7CgkJCX0KCQkJcmV0dXJuOwoJCX0KCgkJaW50IGNvcnJlY3QgPSAwLCB0b3RhbCA9IDA7CgkJZm9yIChpbnQgaT0wOzsgKytpKSB7CgkJCWludCB4ID0gcnVuX3Rlc3RfY2FzZShpKTsKCQkJaWYgKHggPT0gLTEpIHsKCQkJCWlmIChpID49IDEwMCkgYnJlYWs7CgkJCQljb250aW51ZTsKCQkJfQoJCQljb3JyZWN0ICs9IHg7CgkJCSsrdG90YWw7CgkJfQoKCQlpZiAodG90YWwgPT0gMCkgewoJCQljZXJyIDw8ICJObyB0ZXN0IGNhc2VzIHJ1bi4iIDw8IGVuZGw7CgkJfSBlbHNlIGlmIChjb3JyZWN0IDwgdG90YWwpIHsKCQkJY2VyciA8PCAiU29tZSBjYXNlcyBGQUlMRUQgKHBhc3NlZCAiIDw8IGNvcnJlY3QgPDwgIiBvZiAiIDw8IHRvdGFsIDw8ICIpLiIgPDwgZW5kbDsKCQl9IGVsc2UgewoJCQljZXJyIDw8ICJBbGwgIiA8PCB0b3RhbCA8PCAiIHRlc3RzIHBhc3NlZCEiIDw8IGVuZGw7CgkJfQoJfQoKCWludCB2ZXJpZnlfY2FzZShpbnQgY2FzZW51bSwgY29uc3QgaW50ICZleHBlY3RlZCwgY29uc3QgaW50ICZyZWNlaXZlZCwgY2xvY2tfdCBlbGFwc2VkKSB7CgkJY2VyciA8PCAiRXhhbXBsZSAiIDw8IGNhc2VudW0gPDwgIi4uLiAiOwoKCQlzdHJpbmcgdmVyZGljdDsKCQl2ZWN0b3I8c3RyaW5nPiBpbmZvOwoJCWNoYXIgYnVmWzEwMF07CgoJCWlmIChlbGFwc2VkID4gQ0xPQ0tTX1BFUl9TRUMgLyAyMDApIHsKCQkJc3ByaW50ZihidWYsICJ0aW1lICUuMmZzIiwgZWxhcHNlZCAqICgxLjAvQ0xPQ0tTX1BFUl9TRUMpKTsKCQkJaW5mby5wdXNoX2JhY2soYnVmKTsKCQl9CgoJCWlmIChleHBlY3RlZCA9PSByZWNlaXZlZCkgewoJCQl2ZXJkaWN0ID0gIlBBU1NFRCI7CgkJfSBlbHNlIHsKCQkJdmVyZGljdCA9ICJGQUlMRUQiOwoJCX0KCgkJY2VyciA8PCB2ZXJkaWN0OwoJCWlmICghaW5mby5lbXB0eSgpKSB7CgkJCWNlcnIgPDwgIiAoIjsKCQkJZm9yIChpbnQgaT0wOyBpPChpbnQpaW5mby5zaXplKCk7ICsraSkgewoJCQkJaWYgKGkgPiAwKSBjZXJyIDw8ICIsICI7CgkJCQljZXJyIDw8IGluZm9baV07CgkJCX0KCQkJY2VyciA8PCAiKSI7CgkJfQoJCWNlcnIgPDwgZW5kbDsKCgkJaWYgKHZlcmRpY3QgPT0gIkZBSUxFRCIpIHsKCQkJY2VyciA8PCAiICAgIEV4cGVjdGVkOiAiIDw8IGV4cGVjdGVkIDw8IGVuZGw7CgkJCWNlcnIgPDwgIiAgICBSZWNlaXZlZDogIiA8PCByZWNlaXZlZCA8PCBlbmRsOwoJCX0KCgkJcmV0dXJuIHZlcmRpY3QgPT0gIlBBU1NFRCI7Cgl9CgoJaW50IHJ1bl90ZXN0X2Nhc2UoaW50IGNhc2VudW1fXykgewoJCXN3aXRjaCAoY2FzZW51bV9fKSB7CgkJY2FzZSAwOiB7CgkJCWludCBiMSAgICAgICAgICAgICAgICAgICAgPSAzOwoJCQlpbnQgcTEgICAgICAgICAgICAgICAgICAgID0gMjsKCQkJaW50IG4xICAgICAgICAgICAgICAgICAgICA9IDU7CgkJCWludCBiMiAgICAgICAgICAgICAgICAgICAgPSA2OwoJCQlpbnQgcTIgICAgICAgICAgICAgICAgICAgID0gMjsKCQkJaW50IG4yICAgICAgICAgICAgICAgICAgICA9IDU7CgkJCWludCBleHBlY3RlZF9fICAgICAgICAgICAgPSA2OwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWludCByZWNlaXZlZF9fICAgICAgICAgICAgPSBHZW9tZXRyaWNQcm9ncmVzc2lvbnMoKS5jb3VudChiMSwgcTEsIG4xLCBiMiwgcTIsIG4yKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9CgkJY2FzZSAxOiB7CgkJCWludCBiMSAgICAgICAgICAgICAgICAgICAgPSAzOwoJCQlpbnQgcTEgICAgICAgICAgICAgICAgICAgID0gMjsKCQkJaW50IG4xICAgICAgICAgICAgICAgICAgICA9IDU7CgkJCWludCBiMiAgICAgICAgICAgICAgICAgICAgPSAyOwoJCQlpbnQgcTIgICAgICAgICAgICAgICAgICAgID0gMzsKCQkJaW50IG4yICAgICAgICAgICAgICAgICAgICA9IDU7CgkJCWludCBleHBlY3RlZF9fICAgICAgICAgICAgPSA5OwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWludCByZWNlaXZlZF9fICAgICAgICAgICAgPSBHZW9tZXRyaWNQcm9ncmVzc2lvbnMoKS5jb3VudChiMSwgcTEsIG4xLCBiMiwgcTIsIG4yKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9CgkJY2FzZSAyOiB7CgkJCWludCBiMSAgICAgICAgICAgICAgICAgICAgPSAxOwoJCQlpbnQgcTEgICAgICAgICAgICAgICAgICAgID0gMTsKCQkJaW50IG4xICAgICAgICAgICAgICAgICAgICA9IDE7CgkJCWludCBiMiAgICAgICAgICAgICAgICAgICAgPSAwOwoJCQlpbnQgcTIgICAgICAgICAgICAgICAgICAgID0gMDsKCQkJaW50IG4yICAgICAgICAgICAgICAgICAgICA9IDE7CgkJCWludCBleHBlY3RlZF9fICAgICAgICAgICAgPSAyOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWludCByZWNlaXZlZF9fICAgICAgICAgICAgPSBHZW9tZXRyaWNQcm9ncmVzc2lvbnMoKS5jb3VudChiMSwgcTEsIG4xLCBiMiwgcTIsIG4yKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9CgkJY2FzZSAzOiB7CgkJCWludCBiMSAgICAgICAgICAgICAgICAgICAgPSAzOwoJCQlpbnQgcTEgICAgICAgICAgICAgICAgICAgID0gNDsKCQkJaW50IG4xICAgICAgICAgICAgICAgICAgICA9IDEwMDUwMDsKCQkJaW50IGIyICAgICAgICAgICAgICAgICAgICA9IDQ4OwoJCQlpbnQgcTIgICAgICAgICAgICAgICAgICAgID0gMTAyNDsKCQkJaW50IG4yICAgICAgICAgICAgICAgICAgICA9IDEwMDA7CgkJCWludCBleHBlY3RlZF9fICAgICAgICAgICAgPSAxMDA1MDA7CgoJCQljbG9ja190IHN0YXJ0X18gICAgICAgICAgID0gY2xvY2soKTsKCQkJaW50IHJlY2VpdmVkX18gICAgICAgICAgICA9IEdlb21ldHJpY1Byb2dyZXNzaW9ucygpLmNvdW50KGIxLCBxMSwgbjEsIGIyLCBxMiwgbjIpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0KCgkJLy8gY3VzdG9tIGNhc2VzCgovKiAgICAgIGNhc2UgNDogewoJCQlpbnQgYjEgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgcTEgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgbjEgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgYjIgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgcTIgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgbjIgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgZXhwZWN0ZWRfXyAgICAgICAgICAgID0gOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWludCByZWNlaXZlZF9fICAgICAgICAgICAgPSBHZW9tZXRyaWNQcm9ncmVzc2lvbnMoKS5jb3VudChiMSwgcTEsIG4xLCBiMiwgcTIsIG4yKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9Ki8KLyogICAgICBjYXNlIDU6IHsKCQkJaW50IGIxICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IHExICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IG4xICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IGIyICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IHEyICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IG4yICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IGV4cGVjdGVkX18gICAgICAgICAgICA9IDsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlpbnQgcmVjZWl2ZWRfXyAgICAgICAgICAgID0gR2VvbWV0cmljUHJvZ3Jlc3Npb25zKCkuY291bnQoYjEsIHExLCBuMSwgYjIsIHEyLCBuMik7CgkJCXJldHVybiB2ZXJpZnlfY2FzZShjYXNlbnVtX18sIGV4cGVjdGVkX18sIHJlY2VpdmVkX18sIGNsb2NrKCktc3RhcnRfXyk7CgkJfSovCi8qICAgICAgY2FzZSA2OiB7CgkJCWludCBiMSAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBxMSAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBuMSAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBiMiAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBxMiAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBuMiAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBleHBlY3RlZF9fICAgICAgICAgICAgPSA7CgoJCQljbG9ja190IHN0YXJ0X18gICAgICAgICAgID0gY2xvY2soKTsKCQkJaW50IHJlY2VpdmVkX18gICAgICAgICAgICA9IEdlb21ldHJpY1Byb2dyZXNzaW9ucygpLmNvdW50KGIxLCBxMSwgbjEsIGIyLCBxMiwgbjIpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0qLwoJCWRlZmF1bHQ6CgkJCXJldHVybiAtMTsKCQl9Cgl9Cn0KCgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqYXJndltdKSB7CglpZiAoYXJnYyA9PSAxKSB7CgkJbW9qX2hhcm5lc3M6OnJ1bl90ZXN0KCk7Cgl9IGVsc2UgewoJCWZvciAoaW50IGk9MTsgaTxhcmdjOyArK2kpCgkJCW1val9oYXJuZXNzOjpydW5fdGVzdChhdG9pKGFyZ3ZbaV0pKTsKCX0KfQovLyBFTkQgQ1VUIEhFUkUK